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:
ENTRADA |
SAÍDA |
4 5 1 2 2 3 2 4 3 1 3 4 |
4 |