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

Zadanie I - Strajk

Autor: Bartosz Nowierski

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:

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 ≤ AB ≤ 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 Ti i Si (1 ≤ Ti ≤ 1.000, –1 ≤ Si ≤ 1.000.000.000). Ti oznacza liczbę torów w mieście i, a Si 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 Ci (2 ≤ Ci ≤ N). Po niej następuje ciąg par liczb Xi,j i Yi,j (j = 1...Ci). 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