Rak

Limit pamięci: 32 MB

W Bajtocji niedawno zbudowano staw, w którym mieszka żółwi. W każdym z domków, ponumerowanych od 1 do , które się tam znajdują, mieszka dokładnie jeden żółw. W najbliższym czasie do Bajtocji planuje wpaść w odwiedziny rak Wędrownik mieszkający na co dzień w Bajtomeryce. Jest on rakiem bardzo towarzyskim i wszystkie bajtockie żółwie są jego przyjaciółmi. Podczas swojego pobytu, Wędrownik chce się zatrzymać w domku u jednego z nich. Tu powstaje jednak dylemat - wktórym domku powinien mieszkać?

Wędrownika interesują przede wszystkim takie domki, z których mógłby odwiedzać jak najwięcej przyjaciół. Mogłoby się wydawać, że odwiedzanie przyjaciół to żaden problem, ale jednak w bajtockim stawie jest to w pewien sposób utrudnione. Po pierwsze, aby kogoś odwiedzić, trzeba się najpierw dostać do jego domku. Po drugie, trzeba później wrócić z powrotem. Zakładamy również, że Wędrowiec nie odwiedza żółwia, u którego mieszka.

Wędrowiec porusza się zgodnie z następującymi zasadami:

• Między domkami może się przemieszczać jedynie po wyznaczonych trasach.
• Każda z tras jest jednokierunkowa i łączy dwa różne domki. Może istnieć kilka tras łączących te same domki.
• Rak może się poruszać na dwa sposoby - normalnie lub wspak. Jeśli w danym momencie rak porusza się normalnie i znajduje się w domku , to może przejść do domku , jeśli istnieje trasa prowadząca z do . Jeśli porusza się wspak, to może przejść z do tylko po trasie prowadzącej z do .
• Niektóre trasy są specjalne. Jeśli rak przejdzie taką trasą, to zaraz po tym rak zmienia swój sposób poruszania - jeśli chodził normalnie, to odtąd chodzi wspak, a jeśli chodził wspak, to będzie chodził normalnie. Rak nie może zmieniać sposobu poruszania się nigdzie indziej.
• Idąc w odwiedziny, Wędrownik wychodzi ze swojego miejsca zamieszkania, poruszając się wspak. W czasie pobytu u przyjaciela rak nie zmienia swojego sposobu poruszania się. W momencie powrotu do domu Wędrownik musi się poruszać wspak (jeśli ostatnia trasa jest specjalna, to przed wejściem na nią powinien był poruszać się normalnie).

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis tras łączących domki w bajtockim stawie,
• dla każdego domku obliczy ilość przyjaciół, których mógłby odwiedzać Wędrowiec, gdyby zamieszkał w tym domku,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ), oznaczające odpowiednio ilość domków i ilość tras. W kolejnych wierszach znajdują się opisy poszczególnych tras, po jednym w każdym wierszu. Opis trasy składa się z trzech liczb , i (, ). Liczba to numer domku, w którym trasa się zaczyna, to numer domku, w którym się kończy. Trasa jest specjalna, jeśli .

Wyjście

Twój program powinien wypisać na standardowe wyjście dokładnie wierszy. W -tym z nich powinna się znaleźć liczba przyjaciół, których mógłby odwiedzić Wędrowiec, gdyby mieszkał w domku numer .

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

3
3
3
3
0

Mieszkając w domku numer 1, rak może odwiedzić przyjaciół w domkach 2, 3, 4. Mieszkając w domku numer 2, rak może odwiedzić przyjaciół w domkach 3, 4, 5. Mieszkając w domku numer 3, rak może odwiedzić przyjaciół w domkach 2, 4, 5. Mieszkając w domku numer 4, rak może odwiedzić przyjaciół w domkach 2, 3, 5. Mieszkając w domku numer 5, rak nie może odwiedzić żadnego przyjaciela.

Autor zadania: Szymon Acedański.