Avaries P67717

La xarxa de trens d’un país molt petit està formada per $n$ estacions, unides entre sí per $m$ vies bidireccionals. La xarxa és connexa. Com que es volen acollir els propers Jocs Olímpics d’Hivern, el govern del país ha decidit fer un estudi de la robustesa de la xarxa de transport. En particular, es vol saber, per a cada estació $x$, en quants components connexos quedaria separada la xarxa si hi hagués una avaria. Podeu calcular-ho eficientment?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$, seguits d’$m$ parells $x$ $y$, indicant una via entre $x$ i $y$, amb $x \ne y$. Les estacions es numeren entre 0 i $n-1$. No hi ha vies repetides. Podeu suposar $2 \le n \le 10^5$ i $1 \le m \le 3 \cdot 10^5$.

Sortida

Per cada cas, i per a cada estació, indiqueu el nombre de components connexos en què quedaria dividida la xarxa si hi hagués una avaria en aquella estació. Escriviu una línia amb 10 guions al final de cada cas.

Puntuació

• Cas A:   Casos on la xarxa té, com a molt, un cicle.

• Cas B:   Resta de casos.

Observació

Us recomanem resoldre aquest problema en C++.