Se da un graf neorientat simplu cu n noduri si m muchii. Atribuiti fiecarei componente conexe o eticheta , in ordinea in care este intalnita prima data parcurgand nodurile de la 1 la n, incepand cu eticheta 1. Afisati eticheta fiecarui nod.
- Date de intrare
- Pe prima linie se citesc n si m. Urmeaza m linii, fiecare cu doua numere reprezentand o muchie.
- Date de iesire
- Se afiseaza n numere separate prin spatiu: eticheta componentei nodului 1, 2, ..., n.
- Restrictii
- 1 <= n <= 100000, 0 <= m <= 200000
Exemple
Exemplul 1
Intrare
6 3 1 2 2 3 4 5
Iesire
1 1 1 2 2 3
Exemplul 2
Intrare
4 0
Iesire
1 2 3 4