Lordzie Gleboryju, władco wszystkich krasnoludów, elfy znów atakują! Ich hordy wciąż są daleko, lecz trzeba się przed nimi zabezpieczyć zawczasu.
W Twoim księstwie jest n miast, niektóre z nich są połączone dwukierunkowymi drogami. Krasnoludy (pewnie przeciwnie do elfów) mądrze budują drogi: każda droga łączy dwa różne miasta i nie ma dwóch dróg łączących tę samą parę miast. Co więcej, z każdego miasta da się dojechać do każdego używając krasnoludzkich dróg. Miasta - porządek krasnoludzki musi być - są ponumerowane liczbami naturalnymi od 1 do n. Stolica jest w mieście o numerze T.
Nie wierzysz, by te głupie elfy były w stanie zniszczyć więcej niż jedną drogę. No, ale jedną to może im się uda. Wydałeś już odpowiednie polecenia i pewnie to nie nastąpi, ale później, przy kielichu wina wymyśliłeś zagadkę: dla każdego miasta w królestwie obliczyć, ile jest różnych dróg takich, że ich zniszczenie spowoduje, że z tego miasta nie da się dojechać do stolicy.
W wejściu w pierwszej linii są trzy liczby całkowite: 1 <= n <= 200 000, n-1 <= m <= 500 000 i 1 <= T <= n, oznaczające liczbę miast, liczbę dróg, oraz numer stolicy. Kolejne m wierszy to opisy dróg: dwie liczby - numery miast będących końcem tej drogi.
Wypisać w jednej linii należy n liczb oddzielonych spacją: wyniki dla kolejnych miast. Dla stolicy wynikiem jest oczywiście 0.
Dla danych:
11 13 2 1 2 2 3 3 1 1 11 3 10 2 4 4 5 5 6 4 6 6 7 7 8 7 9 8 9
prawidłowym wynikiem jest:
0 0 0 1 1 1 2 2 2 1 1
[Zgłoś rozwiązanie] [Moje zgłoszenia]