Skarb

Limit pamięci: 32 MB

Król Bajtazar ukrywał w swym zamku skarb, a miejsce jego ukrycia trzymał w tajemnicy. Kiedy jednak wyruszał na wojnę bał się, że może zginąć i skarb przepadnie. Wybrał więc zaufanych strażników i każdemu powierzył część informacji potrzebnych do odnalezienia skarbu. Następnie rozkazał strażnikom zejść do lochów rozciągających się pod zamkiem (każdemu w inne miejsce) i chodzić po lochach metodą prawej ręki. Lochy to podziemne komnaty połączone korytarzami. Korytarze nie przecinają się poza komnatami. Korytarz może przebiegać pod innymi korytarzami. Metoda prawej ręki polega na tym, że strażnik po wejściu do komnaty wychodzi z niej pierwszym korytarzem po prawej stronie. Strażnicy rozpoczynają wędrówkę przy wejściach do korytarzy, zatem może się zdarzyć, że wielu strażników zaczyna wędrówkę wychodząc z tej samej komnaty, jeśli tylko ruszają różnymi korytarzami.

Król wie, że dopóki nie powróci z wojny lub nie polegnie, każdy ze strażników będzie wiernie wykonywał jego rozkazy. Jest jednak świadom, że gdy tylko dwóch (lub więcej) strażników spotka się w komnacie, to nie omieszka wymienić się wszystkimi posiadanymi informacjami dotyczącymi skarbu. Strażnicy nie są samolubni i wymieniają informacje, nawet, jeśli któryś z nich nie dowie się w ten sposób niczego nowego. Jeśli strażnicy rozpoczynają wędrówkę w tej samej komnacie, to od razu wymieniają się informacjami, które początkowo znają. Gdy jednak strażnicy mijają się w korytarzach, to nie rozmawiają ze sobą.

Król zastanawia się, czy gdy wróci szczęśliwie z wojny, skarb będzie nadal bezpieczny. Chce on wiedzieć, którzy strażnicy mogą poznać wszystkie informacje potrzebne do odnalezienia skarbu.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis lochów, początkowe położenie strażników, komnaty, do których pójdą najpierw, oraz informacje dotyczące skarbu, jakie każdy ze strażników początkowo zna,
• wyznaczy strażników, którzy mogą kiedyś poznać wszystkie informacje potrzebne do odnalezienia skarbu,
• wypisze numery tych strażników na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita . Jest to liczba komnat w lochach, . Komnaty są ponumerowane od 1 do . W kolejnych wierszach opisane są korytarze łączące komnaty. W wierszu opisane są korytarze wychodzące z komnaty nr , w kolejności zgodnej z ruchem wskazówek zegara. W każdym z tych wierszy znajdują się liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza z tych liczb, , to liczba korytarzy wychodzących z komnaty nr , . Dalej w tym samym wierszu zapisanych jest liczb całkowitych - każdy z wychodzących korytarzy jest opisany dwiema liczbami całkowitymi. Pierwsza z liczb opisujących korytarz to numer komnaty, do której on prowadzi. Druga z tych liczb to jego długość, liczba całkowita z zakresu od 1 do 100. Korytarze są dwukierunkowe, tzn. jeżeli z komnaty wychodzi korytarz długości prowadzący do komnaty , to z komnaty wychodzi korytarz długości prowadzący do komnaty . Każda para komnat może być połączona co najwyżej jednym korytarzem. Strażnik potrzebuje na przejście korytarzem dokładnie tyle czasu, ile wynosi jego długość. Zakładamy, że czas spędzany przez strażników w komnatach jest pomijalny.

W wierszu zapisane są dwie liczby całkowite i , , , gdzie to liczba strażników, a to liczba informacji potrzebnych do odnalezienia skarbu. Strażnicy są ponumerowani od 1 do . Informacje dotyczące skarbu są ponumerowane od 1 do . W kolejnych wierszach opisani są strażnicy, w wierszu opisany jest strażnik nr . W każdym z tych wierszy zapisane są liczby całkowite pooddzielane pojedynczymi odstępami. Pierwsza liczba w wierszu to numer komnaty, w której początkowo znajduje się strażnik. Druga liczba to numer komnaty, do której strażnik ruszy jako pierwszej. Trzecia liczba, , to liczba informacji dotyczących skarbu, które strażnik nr początkowo zna, . Dalej w wierszu znajduje się liczb całkowitych - numery informacji znanych początkowo strażnikowi nr .

Wyjście

W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą - liczbę strażników, którzy mogą kiedyś poznać wszystkie informacje potrzebne do odnalezienia skarbu. W następnych wierszach powinny znaleźć się uporządkowane rosnąco numery tych strażników, po jednym w wierszu.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

2
2
3

Autor zadania: Adam Borowski.