Informática - Nível Avançado - Semana 4

Laurêncio e o Grafo Vazio

Durante uma de suas viagens, Laurêncio descobriu um grafo diferente - um grafo vazio! O grafo era formado por $N$ vértices, mas nenhuma aresta. Apenas por diversão, os seus amigos de viagem, Legal e Sams, lhe deram $M$ pedidos: cada pedido constiste de dois vértices do grafo, $u_i$ e $v_i$.

Laurêncio quer descobrir o menor número de arestas direcionadas necessárias tal que, ao adicioná-las no grafo, existe um caminho de $u_i$ a $v_i$ para cada pedido $(u_i, v_i)$.

Entrada

A primeira linha consiste de dois inteiros: $N$ e $M$.
As próximas $M$ linhas contém, cada uma, dois inteiros, $u_i$ e $v_i$ - o $i$-ésimo pedido.

Saída

Imprima apenas um inteiro: O menor número de arestas direcionadas necessárias para cumprir os pedidos.

Restrições

• $1 \leq N, M \leq 10^5$
• $1 \leq u_i, v_i \leq N$

Exemplos:

4 5
1 2
2 3
2 4
3 1
3 4

4

Para submeter sua solução use esse link.