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ż jedno miasto. No, ale jedno 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 miast (różnych od stolicy i tego miasta) takich, że ich zniszczenie spowoduje, że z tego miasta nie da się dojechać do stolicy. Przez zniszczone miasto nie można oczywiście jechać.
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:
9 10 1 1 2 2 3 3 1 3 4 4 5 5 6 6 4 6 7 2 8 1 9
prawidłowym wynikiem jest:
0 0 0 1 2 2 3 1 0
[Zgłoś rozwiązanie] [Moje zgłoszenia]