W kraju działają agenci obcych wywiadów. Zajmują się oni nie tylko wykradaniem tajemnic, ale także nawzajem się szpiegują. Mówimy, że agent A rozpracował agenta B, jeśli A posiada dokumenty wystarczające do aresztowania B.

Niektórzy agenci są przekupni - w zamian za odpowiednią sumę pieniędzy są gotowi oddać wszystkie posiadane dokumenty. Aresztując agenta przechwytujemy wszystkie zgromadzone przez niego dokumenty. Przekupienie odpowiednio wybranych agentów może więc uruchomić łańcuch aresztowań prowadzący do zlikwidowania wszystkich agentów działających w kraju.

Rodzimy kontrwywiad dostarczył nam informacje o tym, jacy obcy agenci działają w kraju, którzy z nich są przekupni i za jaką cenę, a także, którzy agenci rozpracowali których. Liczba agentów n <= 3000; są oni ponumerowani od 1 do n.

Zadanie

• wczytuje z pliku tekstowego AGE.IN dane zgromadzone przez kontrwywiad,
• stwierdza, czy jest możliwe, by przez przekupienie odpowiednio wybranych agentów uzyskać informacje, uruchamiające łańcuch prowadzący do aresztowania wszystkich agentów w kraju i jeśli tak, oblicza minimalny koszt takiego zakupu, a jeśli nie, znajduje numer jednego z agentów, którego nie będzie można aresztować,
• zapisuje wynik do pliku tekstowego AGE.OUT.

Wejście

• W pierwszym wierszu pliku tekstowego AGE.IN jest zapisana jedna liczba naturalna n. Jest to liczba wszystkich działających w kraju agentów, 1 <= n <= 3000.
• W drugim wierszu jest zapisana jedna liczba naturalna p. Jest to liczba wszystkich agentów przekupnych, 1 <= p <= n.
• W kolejnych p wierszach są zapisane informacje o przekupnych agentach. W każdym takim wierszu są zapisane dwie liczby całkowite dodatnie oddzielone odstępem - pierwsza z nich jest numerem przekupnego agenta, a druga to suma, za którą można go przekupić - jest to liczba nie większa niż 20000.
• Kolejny wiersz zawiera jedną liczbę r, gdzie 1 <= r <= 8000. Jest to liczba takich par (A,B), że agent A rozpracował agenta B.
• W następnych r wierszach podane są wszystkie takie pary. W każdym z tych wierszy są zapisane dwie różne liczby ze zbioru {1, 2, ... , n} oddzielone odstępem - pierwsza, to numer agenta, który rozpracował, a druga, to numer agenta, który został rozpracowany.

Wyjście

• W pierwszym wierszu pliku tekstowego AGE.OUT należy zapisać jedno słowo: TAK - jeśli istnieje możliwość aresztowania wszystkich agentów działających w kraju, albo NIE - jeśli taka możliwość nie istnieje.
• W drugim wierszu należy zapisać jedną liczbę całkowitą dodatnią: minimalny koszt zakupu informacji wystarczających, by doprowadzić do aresztowania wszystkich agentów w kraju, albo numer dowolnego agenta, którego nie da się zaaresztować.

Przykłady
Dla pliku AGE.IN:
3
2
1 10
2 100
2
1 3
2 3
 
w pliku AGE.OUT należy zapisać:
TAK
110
 
Dla pliku AGE.IN:
4
2
1 100
4 200
2
1 2
3 4
 
w pliku AGE.OUT należy zapisać:
NIE
3

Twój program powinien szukać pliku AGE.IN w katalogu bieżącym i tworzyć plik AGE.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę AGE.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku AGE.EXE.