바다 이야기

젊은 바이텐손은 항구의 선술집에서 시간을 보내는 것을 좋아합니다. 그곳에서는 늙은 뱃사람들이 자신의 항해 이야기를 들려줍니다. 처음에는 아무리 믿기 힘든 이야기라도 모두 믿었지만, 시간이 지나면서 점점 의심이 들기 시작했습니다. 결국 그는 그 이야기들에 조금이라도 진실이 담겨 있는지 검증하는 프로그램을 만들기로 했습니다. 뱃사람이 정말로 모든 폭풍을 헤쳐 나왔는지는 알 수 없지만, 적어도 그가 말한 여정이 앞뒤가 맞는지는 확인할 수 있다고 생각했지요. 하지만 바이텐손은 프로그래머가 아니니, 그를 도와주세요.

뱃사람들이 오가는 바다에는 $n$개의 항구와 이들을 잇는 $m$개의 항로가 있습니다. 항로는 두 항구를 직접 연결하며, 양방향 모두로 항해할 수 있습니다. 바이텐손은 모두 $k$개의 이야기를 들었습니다. 각 이야기는 한 항구에서 출발하여 여러 항로를 거친 뒤 다른 항구(출발한 항구와 같을 수도 있습니다)에 도착한 뱃사람의 여정을 담고 있습니다. 뱃사람은 같은 항로를 여러 번, 그리고 매번 어느 방향으로든 지날 수 있습니다.

첫째 줄에 세 정수 $n$, $m$, $k$ ($2 \le n \le 5000$, $1 \le m \le 5000$, $1 \le k \le 10^6$)가 주어집니다. 각각 항구의 수, 항로의 수, 이야기의 수를 뜻합니다.

이어지는 $m$개의 줄에는 각각 항로 하나를 나타내는 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 공백으로 구분되어 주어집니다. 이는 항구 $a$와 $b$를 잇는 항로를 뜻합니다.

그다음 $k$개의 줄에는 각각 세 정수 $s$, $t$, $d$ ($1 \le s, t \le n$, $1 \le d \le 10^9$)가 공백으로 구분되어 주어집니다. 이는 이야기 속 뱃사람이 항구 $s$에서 출발하여 항구 $t$에서 여정을 마쳤으며, 항로를 정확히 $d$번 지났음을 뜻합니다.

정확히 $k$개의 줄을 출력합니다. $i$번째 줄에는 입력 순서로 $i$번째 이야기의 여정이 가능하면 TAK(폴란드어로 “예”)를, 불가능하면 NIE(폴란드어로 “아니오”)를 출력합니다.