Problem description

Amelia i Tymon uwielbiają chodzić na długie spacery. Szczególnie często zdarza się, że Tymon odprowadza Amelię ze szkoły do jej domu. Żeby urozmaicić sobie przechadzki, starają się wybierać różne możliwe trasy.

Sieć spacerową Amelii i Tymona można opisać jako N skrzyżowań połączonych drogami. Szkoła znajduje się przy skrzyżowaniu o numerze 1, a dom Amelii przy skrzyżowaniu o numerze N. Para nie chce krążyć zbyt długo przed dotarciem do domu, dlatego po każdej drodze łączącej dwa skrzyżowania mogą przejść tylko w jednym kierunku. Nie chcieliby również trafić dwukrotnie do skrzyżowania, przez które już przechodzili. Można zatem powiedzieć, że ich sieć spacerowa stanowi acykliczny graf skierowany.

Tomek, który jest dobrym znajomym Amelii i Tymona, został ostatnio głównym inspektorem do spraw rozbudowy dróg w ich mieście. Tymon poprosił Tomka, żeby ten rozbudował drogi w mieście w taki sposób, żeby liczba różnych możliwych tras spacerowych ze szkoły do domu Amelii była podzielna przez K. Tomek, jak to dobry kumpel, chciałby spełnić prośbę Tymona. Jednakże, skoro dopiero awansował na swoje stanowisko, nie chciałby, żeby rozbudowa była zbyt duża. Zdecydował zatem, że może pozwolić sobie jedynie na wybranie już istniejącej pary skrzyżowań, między którymi istnieje droga, a następnie zwielokrotnienie tej drogi (tzn. z jednego skrzyżowania do drugiego można będzie przejść na wiele sposobów, a nie tylko jeden). Tomek dla każdej ulicy chciałby zatem wiedzieć, ile razy co najmniej powinna ona zostać zwielokrotniona lub dowiedzieć się, że nie da się jej zwielokrotnić tak, żeby spełnić jego oczekiwania. Zadanie znalezenia odpowiedzi powierzył Tobie!

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby naturalne N, M oraz K, oznaczające kolejno liczbę skrzyżowań, liczbę dróg oraz stałą wyznaczoną przez Tymona. W następnych M wierszach następuje opis dróg w mieście Amelii i Tymona. Każdy opis składa się z pary dwóch liczb u i v oznaczających, że istnieje droga ze skrzyżowania u do skrzyżowania o numerze v.

Wyjście

Należy wypisać M wierszy na standardowe wyjście. W i-tym wierszu powinna znajdować się jedna liczba całkowita opisująca ile co najmniej razy i-ta droga musi zostać zwielokrotniona, aby liczba ścieżek ze szkoły do domu Amelii była podzielna przez K lub liczba  − 1 jeżeli to nie jest możliwe.

Ograniczenia

1 ≤ N, M ≤ 1 000 000, 2 ≤ K ≤ 10⁹. Można założyć, że graf na wejściu jest acykliczny i spójny, oraz że każda krawędź u, v podana na wejści spełnia warunek u < v.

Przykład

4 5 4
1 2
2 3
2 4
3 4
1 4

-1
2
2
2
2