Rezolvare PBinfo #1707

Cerința

Se consideră o rețea formată din n servere, numerotate de la 1 la n. În rețea există m perechi de servere x y cunoscute între care există legături de comunicație directe. Între oricare două servere din rețea există legături, fie directe, fie prin intermediul altor servere.

Stabiliți pentru fiecare dintre cele n servere dacă eliminarea sa din rețea conduce la pierderea legăturii dintre cel puțin două servere rămase.

Date de intrare

Fișierul de intrare retea.in conține pe prima linie numerele n si m. Pe următoarele m linii se vor afla câte două numere naturale x y, reprezentând perechi de servere între care există legături directe.

Date de ieșire

Fișierul de ieșire retea.out va conține pe prima linie n numere naturale 0 sau 1:

• al i-lea număr va fi 0 dacă prin eliminarea serverului cu numărul i rămân legături între oricare două servere rămase
• al i-lea număr va fi 1 dacă prin eliminarea sa se pierde legătura între cel puțin două servere rămase.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ x,y ≤ n

Exemplu:

retea.in

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

retea.out

0 0 1 1 0

Explicație

Serverul 1 daca este eliminat nu întrerupe legătura deoarece exista lanțul de legături 2 - 3 - 4 - 5 pe care nu îl afectează.
Serverul 2 dacă este eliminat nu întrerupe legătura deoarece exista lanțul de legături 1 - 3 - 4 - 5 pe care nu îl afectează.
Serverul 3 dacă este eliminat, serverele 1 și 2 nu mai pot comunica cu serverele 4 și 5.
Serverul 4 daca este eliminat, serverele 1, 2 și 3 nu mai pot comunica cu serverul 5.
Serverul 5 dacă este eliminat nu întrerupe legătura deoarece serverele 1, 2, 3, 4 sunt legate intre ele.