요원

어느 나라가 외국 첩보 기관에서 보낸 요원들로 넘쳐난다. 이들은 기밀 정보를 훔칠 뿐 아니라 서로를 감시하기도 한다. 요원 $A$가 요원 $B$를 체포하기에 충분한 문서를 모았다면, $A$가 $B$를 적발했다고 한다.

일부 요원은 뇌물을 받는다. 정해진 금액을 주면 자신이 가진 문서를 모두 넘긴다. 따라서 어떤 요원들을 매수하면 연쇄 체포를 시작할 수 있고(요원을 체포하면 그 요원의 문서를 모두 확보한다), 이 연쇄가 나라 안의 모든 요원을 소탕하는 데까지 이어질 수 있다.

방첩 당국은 나라 안 외국 요원의 수, 누구를 얼마에 매수할 수 있는지, 그리고 누가 누구를 적발했는지를 알려 주었다. 요원은 모두 $n$명이며($n \le 3000$), $1$번부터 $n$번까지 번호가 붙어 있다.

다음을 수행하는 프로그램을 작성하라.

• 방첩 당국이 준 정보를 표준 입력에서 읽는다.
• 일부 요원을 매수해 시작되는 연쇄 체포로 나라 안 모든 요원을 소탕할 수 있는지 판정하고, 가능하면 그 최소 매수 비용을 구한다. 불가능하면 체포도 매수도 할 수 없는 요원의 번호를 찾는다.
• 결과를 표준 출력에 쓴다.

첫째 줄에 나라에서 활동하는 요원의 수 $n$이 주어진다($1 \le n \le 3000$).

둘째 줄에 뇌물을 받는 요원의 수 $p$가 주어진다($1 \le p \le n$). 이어지는 $p$개의 줄에는 각각 두 정수가 주어지는데, 첫 번째는 요원의 번호이고 두 번째는 그 요원이 받아들이는 최소 뇌물 액수로 $20000$을 넘지 않는다.

그다음 줄에 정수 $r$가 주어진다($1 \le r \le 8000$). 이는 요원 $A$가 요원 $B$를 적발한 쌍 $(A, B)$의 개수이다. 이어지는 $r$개의 줄에는 각각 $\{1, 2, \ldots, n\}$에 속하는 서로 다른 두 정수가 공백 하나로 구분되어 주어진다. 앞의 수는 적발한 요원의 번호, 뒤의 수는 적발당한 요원의 번호이다.

첫째 줄에는 나라 안 모든 요원을 소탕할 수 있으면 TAK(폴란드어로 "예"), 그렇지 않으면 NIE(폴란드어로 "아니요")를 출력한다.

• 소탕할 수 있으면, 둘째 줄에 모든 요원을 소탕하는 연쇄 체포를 시작하기 위한 최소 매수 비용을 정수 하나로 출력한다.
• 소탕할 수 없으면, 둘째 줄에 체포도 매수도 할 수 없는 요원의 번호를 출력한다. 그런 요원이 여럿이면 번호가 가장 작은 요원을 출력한다.