Powrót głupich elfów

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ć.

Wejście, wyjście

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.

Przykład

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