Na terenie Chin znajduje się wiele muzeów oferujących zwiedzającym bogactwo ciekawych eksponatów. Zgromadzone zbiory są bardzo cenne, więc Chińskie Ministerstwo Kultury szczególnie dba o ich bezpieczeństwo. Wszystkie sale w muzeach są monitorowane, jednak jak ostatnio odkryto nie zapewnia to całkowitego bezpieczeństwa. Powodem problemów jest fakt, że choć kamer jest wystarczająco dużo, to czasami brakuje monitorów, więc na pojedynczym monitorze pokazywany jest cyklicznie obraz z wielu kamer. Okazuje się, że przechodząc między salami w odpowiednim czasie, złodzieje mogą wynieść cenny eksponat niezauważeni.
Sytuacja ta musi zostać jak najszybciej naprawiona, ale wcześniej należy dokładnie zbadać bezpieczeństwo cennych eksponatów we wszystkich muzeach. W tym celu właśnie zatrudniono Ciebie. Twoim zadaniem jest napisanie programu, który na podstawie opisu topologii muzeum i opisu działania kamer stwierdzi czy możliwe jest wejście do muzeum, przejście do sali zawierającej cenne eksponaty i wyjście niezauważonym (strażnicy są bardzo czujni, więc nie jest możliwe aby ktoś pojawił się na monitorze, a strażnik tego nie zauważył). Jeżeli jest to możliwe, to należy obliczyć najkrótszy czas w jakim można tego dokonać. Uważaj! Złodziej może wejść do muzeum w dowolnej chwili i poruszać się dowolnie szybko! Zakładamy, że można przejść z sali A do sali B niezauważonym dokładnie w momencie przełączania obrazu z kamer, w sytuacji gdy przed przełączeniem nie był wyświetlany obraz z sali A, a po przełączeniu nie jest wyświetlany obraz z sali B.
W pierwszym wierszu danych wejściowych znajduje się pojedyncza liczba całkowita oznaczająca liczbę muzeów w Chinach. Dalej znajdują się kolejne opisy wszystkich muzeów. Pierwszy wiersz opisu muzeum zawiera dwie liczby: S, D oznaczające odpowiednio liczbę sal (1 ≤ S ≤ 1000) oraz liczbę drzwi (0 ≤ D ≤ 7000). W kolejnych D wierszach znajdują się po dwie różne liczby – numery sal między którymi istnieją drzwi (sale numerowane są od 1 do S, a między każdą parą sal znajdują się co najwyżej jedne drzwi). Następna linia zawiera liczbę M oznaczającą liczbę monitorów (0 ≤ M ≤ 10000). Dalsze M linii zawiera opisy działania monitorów. Pojedynczy opis działania monitora zawiera liczbę całkowitą K oznaczającą liczbę podłączonych kamer (1 ≤ K ≤ 10) i K liczb oznaczających numery sal kolejno pokazywanych na danym monitorze (przełączenia widoków następują jednocześnie na wszystkich monitorach w dziesięciosekundowych odstępach czasu; zaraz po włączenia systemu monitoringu monitory wyświetlają obraz z sali, której numer występuje jako pierwszy). Kolejny wiersz zawiera liczbę E oznaczającą liczbę sal, w których znajdują się cenne eksponaty (w całych Chinach jest nie więcej niż 50 takich sal). Ostatni wiersz zawiera E liczb – numery sal zawierających cenne eksponaty. Jedyne wejście (i zarazem jedyne wyjście) do muzeum znajduje się w sali numer 1.
Kolejne wiersze prawidłowego wyjścia programu zawierają raporty bezpieczeństwa cennych eksponatów z kolejnych sal z kolejnych muzeów (wg kolejności występowania w danych wejściowych). Pojedynczy raport może być napisem „safe” oznaczającym, że eksponaty w danej sali są całkowicie bezpieczne albo liczbą oznaczającą najmniejszy czas (w sekundach), w którym można wejść do muzeum, przejść przez wyznaczoną salę i wyjść niezauważonym.
4 6 6 1 2 2 3 3 4 4 5 5 6 6 1 3 3 2 3 4 3 6 1 2 3 3 5 6 1 3 16 28 1 2 1 5 5 6 5 9 9 10 9 13 13 14 2 3 2 6 6 7 6 10 10 11 10 14 14 15 3 4 3 7 7 8 7 11 11 12 11 15 15 16 4 1 4 8 8 5 8 12 12 9 12 16 16 13 12 4 1 2 3 4 4 3 4 1 2 4 4 1 2 3 4 5 8 7 6 4 7 6 5 8 4 8 7 6 5 4 9 10 11 12 4 10 11 12 9 4 11 12 9 10 4 14 13 16 15 4 15 14 13 16 4 16 15 14 13 2 13 15 3 2 1 2 2 3 2 2 1 2 2 2 3 2 3 1 3 2 1 2 2 3 2 2 2 3 3 1 2 3 1 3
40 70 110 safe 0 20
(Opis podany tutaj tylko dla rozwiania ewentualnych wątpliwości)