In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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:
Napisz program, który:
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 .
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 .
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.