VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Pan B. wybiera się na konkurs w programowaniu zespołowym, odbywający się następnego dnia w zupełnie innym regionie kraju. Chce na miejscu znaleźć się jak najwcześniej by jak najszybciej pójść spać (na konkursie trzeba być wyspanym). Jedyny środek transportu jaki Pan B. może użyć to pociąg. Niestety PKP (Państwowa Korporacja Pociągowa) zapowiedziała strajk tego dnia, polegający na nie wypuszczaniu pociągów z miast objętych strajkiem. Jest jednak bardzo prawdopodobne, że nie we wszystkich miastach kolejarze będą strajkować, a ci którzy będą, być może zaczną dopiero w późniejszych godzinach. To daje Panu B. szansę na dojechanie do celu. W razie konieczności jest on gotów pojawić się na stacji już o północy w dniu wyjazdu (ale nie wcześniej!).
Mówiąc nieco konkretniej, sytuacja wygląda następująco:

• Strajkować mogą tylko kolejarze w miastach, więc nie ma obawy, że pociąg zatrzyma się na środku drogi jeśli tylko miasta będą przejezdne.
• Jeśli w mieście rozpocznie się strajk, będzie on trwać do końca dnia.
• Pociągi kursują na konkretnych liniach, których nie można zmienić (np. pociąg nie może ominąć jakiegoś miasta). Linia jest opisana przez ciąg różnych miast, w których pociąg się zatrzymuje, wraz z godzinami pojawienia się w tych miastach (jest to jednocześnie godzina przyjazdu i odjazdu - przyjmuje się, że okres postoju jest zerowy). Pociąg nie przejeżdża przez żadne miasto, którego nie ma w specyfikacji jego linii.
• Pasażerowie mogą wysiąść w dowolnym mieście, przez które pociąg przejeżdża lub w którym zatrzymuje się na stałe. Jeśli pociąg startuje z miasta lub przejeżdża przez miasto, w którym aktualnie się znajdują, to mogą do niego wsiąść. Można uznać, że czas przesiadki jest zerowy.
• Każde miasto ma pewną charakterystyczną dla siebie liczbę równoległych do siebie torów, na których mogą stać "zablokowane" pociągi (patrz niżej) oraz zatrzymywać się przejeżdżające pociągi. Na każdym torze może jednocześnie być co najwyżej jeden pociąg. Miasto uznajemy za "zablokowane" jeżeli na każdym jego torze stoi zablokowany pociąg.
• Jeżeli miasto strajkuje to nie wypuszcza pociągów. Tzn. z miasta nie wyjedzie żaden pociąg, który ma godzinę odjazdu późniejszą lub równą godzinie rozpoczęcia strajku. Każdy pociąg, który do takiego miast wjedzie jest zostawiany na torze i zostaje uznany za zablokowany.
• Nie zablokowane miasto może wpuszczać pociągi, nawet jeżeli strajkuje. Jeżeli jest to miasto docelowe dla pewnego pasażera, to można uznać, że szczęśliwie dotarł on do celu.
• Gdy pociąg dojedzie do ostatniego miasta na linii, to zostaje usunięty z toru o ile tylko kolejarze w tym mieście, w tej chwili nie strajkują. W przeciwnym wypadku, zostaje zablokowany na torze.
• Nie ma możliwości by pociąg wjechał do miasta, które jest zablokowane. Jeśli jest on już w trasie do zablokowanego miasta, to zatrzymuje się przed miastem i podróżni muszą w nim zostać do końca strajku (czyli na pewno nie krócej niż do końca tego dnia), bo i tak nie mieliby możliwości dotarcia do miasta. Jeżeli jednak pociąg jest w jakimś mieście i kolejne miasto na linii jest już zablokowane (choćby się zablokowało dokładnie w tej samej godzinie, o której miał odjeżdżać), to nie wyjeżdża on z miasta, tym samym blokując tor (tzn. zostaje uznany za zablokowany).
• Gdy choć jeden tor jest wolny, przez miasto może przejechać dowolna liczba pociągów w tym samym momencie. Tutaj jednak trzeba uważać, bo nawet jeśli pociągi przejeżdżają przez miasto w tej samej jednostce czasu to w rzeczywistości jadą jeden za drugim w kolejności swoich numerów (numer jest jednoznacznie określony przez pozycję linii na liście). Na przykład jeśli w mieście są dwa wolne tory i w tej samej chwili chciałyby przez nie przejechać pociągi 1, 2, 3, 4 i 5 oraz 2 i 4 miałyby zostać zablokowane, to 1 i 3 przejadą, ale 5 nie zostanie wpuszczony do miasta.
• Pociąg nie zostaje wypuszczony na trasę (a tym samym w ogóle nie blokuje toru) jeżeli w momencie gdy powinien wyruszyć z pierwszego miasta swojej linii to miasto strajkuje, albo jest zablokowane. (Uwaga! Pociąg "startujący" podlega takim samym regułom kolejności jak pociągi przyjezdne - np. pociąg o numerze 2 zostaje podstawiony na tor dopiero jak pociąg 1 przejedzie, ale zanim pociąg 3 zostanie wpuszczony do miasta.) W przeciwnym wypadku, jest wystawiany na tor i teoretycznie może zostać zablokowany jeśli drugie miasto na jego trasie jest zablokowane.

Zadanie zostało wymyślone na trasie Poznań-Kraków, w dniu strajku PKP, podczas kilkugodzinnego postoju na stacji we Wrocławiu.

Zadanie

Mając dany rozkład jazdy pociągów oraz plany strajkowe kolejarzy określ czy Pan B. może dojechać do celu jeszcze tego samego dnia, a jeśli tak to podaj kiedy najwcześnej może znaleźć się w mieście docelowym.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Każdy zestaw zaczyna się od wiersza zawierającego 4 liczby całkowite: N - liczba miast, M - liczba linii, A - miasto początkowe, B - miasto docelowe (2 ≤ N ≤ 1.000, 1 ≤ M ≤ 1.000, 1 ≤ A, B ≤ N, A ≠ B). Kolejne N wierszy zawiera opisy sytuacji w miastach. W wierszu i-tym (i = 1...N) opisane jest miasto o numerze i dwiema liczbami całkowitymi T_i i S_i (1 ≤ T_i ≤ 1.000, –1 ≤ S_i ≤ 1.000.000.000). T_i oznacza liczbę torów w mieście i, a S_i godzinę rozpoczęcia strajku w nim, lub fakt że strajku nie będzie jeśli wartość ta jest równa –1. Godziny (zarówno strajków jak i przyjazdów/odjazdów) podawane są jako liczba pewnych jednostek czasu, która upłynęła od początku doby (0 to północ; ostatnia jednostka przed północą kolejnego dnia to 1.000.000.000). Ostatnie M wierszy zestawu to opis linii pociągów. W i-tym wierszu (i = 1...M) opisana jest linia o numerze i ciągiem liczb całkowitych. Pierwsza liczba opisu to liczba miast na linii C_i (2 ≤ C_i ≤ N). Po niej następuje ciąg par liczb X_i,j i Y_i,j (j = 1...C_i). X'y oznaczają numery kolejnych miast na linii (są z zakresu od 1 do N i nie powtarzają się), a Y'i to godziny przyjazdów/odjazdów z tychże miast (są z zakresu od 0 do 1.000.000.000 i podane są w kolejności ściśle rosnącej). Łączna liczba miast na wszystkich liniach w zestawie nie przekroczy 150.000.

Specyfikacja wyjścia

Dla każdego zestawu należy wypisać dokładnie jeden wiersz. Powinien on zawierać godzinę (tj. jednostkę czasu), w której Pan B. najwcześniej może pojawić się w docelowym mieście, o ile tylko będzie to możliwe. Jeżeli jednak okaże się to niemożliwe, należy wypisać pojedyncze słowo NIE.

Przykład

Wejście

3
3 3 1 3
1 11
2 -1
3 0
2 1 10 2 20
2 2 15 3 25
2 2 20 3 30
4 3 2 1
2 1
1 -1
1 -1
1 -1
2 4 0 1 1
2 3 0 1 1
2 2 0 1 1
3 3 3 2
1 2
1 2
1 2
3 1 0 2 1 3 2
3 2 0 3 1 1 2
3 3 0 1 1 2 2

Wyjście

30
NIE
2