Problem description
Paul Erdos był jednym z najwybitniejszych matematyków XX w. Był znany nie tylko ze swoich niesamowitych zdolności do rozwiązywania problemów matematycznych, ale także ze swojego specyficznego stylu bycia i poczucia humoru. Jednym z żartów Erdosa, który utrwalił się jako stały element ,,matematycznego folkloru’’ jest tzw. liczba Erdosa.
Definiujemy ją w następujący sposób: Erdos w swojej własnej osobie ma liczbę Erdosa równą 0. Następnie wszyscy Ci, którzy kiedykolwiek napisali z nim jakąś pracę mają liczbę Erdosa równą 1. Wszyscy Ci, którzy napisali z nimi pracę, ale nie napisali pracy z Erdosem, mają liczbę Erdosa równą 2, itd. Jeśli zdarzy się tak, że dany matematyk nie napisał pracy ani z Erdosem, ani z nikim, komu można przypisać pewną dodatnią liczbę Erdosa, to przyjmujemy, że jego liczba Erdosa wynosi − 1. Można powiedzieć, że w ten sposób definiujemy odległość od Erdosa do innych naukowców.
No dobrze, historyjka ładna, ale pewnie chciałbyś już coś zaimplementować (w końcu po coś jest ten Solve). W takim razie napisz program, który dostając listę prac napisanych przez matematyków, dla każdego z nich obliczy jaka jest jego liczba Erdosa.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: N, M oraz E pooddzielane pojedynczymi odstępami i określające odpowiednio: liczbę rozpatrywanych matematyków oraz liczbę napisanych prac oraz numer matematyka, który jest Erdosem (wszystkich rozpatrywanych matematyków numerujemy od 1 do N). W kolejnych M wierszach znajduje się opis napisanych prac. W i-tym wierszu znajdują się dwie liczby całkowite Ai i Bi, oddzielone pojedynczym odstępem, oznaczające, że matematyk o numerze Ai napisał pracę wspólnie z matematykiem Bi. Żadna para podana na wejściu nie powtarza się, matematyk nie może również napisać pracy sam ze sobą.
Wyjście
Twój program powinien wypisać dokładnie N linii. W i-tej linii wyjścia powinna znaleźć się liczba Erdosa i-tego matematyka.
Ograniczenia
1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 1 000 000, 1 ≤ Ai, Bi ≤ N.
W testach wartych łącznie 50% maksymalnej punktacji: N, M ≤ 1000.
Przykład
| Input | Output | |
|
|