총각 파티

바이타자르(Bajtazar)는 곧 결혼을 앞두고 있고, 의리 있는 친구들은 그의 마지막 자유의 나날을 잊지 못할 추억으로 만들어 주려 합니다.

바이토시아(Byteotia)에는 $0$번부터 $n-1$번까지 번호가 매겨진 $n$개의 도시가 있습니다. 일부 도시 쌍은 양방향 도로로 이어져 있지만 대부분의 도로는 공사 중입니다. 남아 있는 도로는, 임의의 두 도시 사이에 도로로 이동하는 경로가 정확히 하나만 존재하도록 하는 만큼만 남아 있습니다. 즉, 열려 있는 도로들은 하나의 트리를 이룹니다.

친구들은 또한 $p$장의 항공권도 준비했습니다. 각 항공권은 어떤 도시 $a$에서 다른 도시 $b$로 가는 편도 비행을 언제든지 한 번 할 수 있게 해 줍니다($b$에서 $a$로는 갈 수 없습니다).

바이타자르는 정해진 도시 $s$에서 여행을 시작해 정해진 도시 $t$에서 끝내려 합니다. 도중에 도로는 자유롭게 이용할 수 있으며, 가진 항공권은 원하는 순서로 모두 사용해야 합니다. 그런데 어떤 도시를 한번 떠나면 다시는 그곳으로 돌아올 수 없어서, 여행 전체에서 같은 도시를 두 번 방문할 수 없습니다.

이 모든 조건을 만족하는 여행이 존재하는지 판단하세요.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 아래 형식으로 주어집니다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$, $p$가 주어집니다($2 \le n \le 100\,000$, $1 \le m \le 1\,000\,000$, $1 \le p \le 1\,000\,000$). 각각 도시의 수, 열려 있는 도로의 수, 항공권의 수입니다. 열려 있는 도로는 항상 트리를 이루므로 $m = n - 1$입니다.

두 번째 줄에는 두 정수 $s$와 $t$가 주어집니다($0 \le s, t \le n-1$). 각각 출발 도시와 도착 도시입니다.

다음 $m$개의 줄에는 도로가 한 줄에 하나씩 주어집니다. 각 도로는 두 정수 $a_i$, $b_i$로 주어지며($0 \le a_i, b_i \le n-1$, $a_i \ne b_i$), 도시 $a_i$와 $b_i$를 잇는 양방향 도로를 뜻합니다.

다음 $p$개의 줄에는 항공권이 한 줄에 하나씩 주어집니다. 각 항공권은 두 정수 $c_i$, $d_i$로 주어지며($0 \le c_i, d_i \le n-1$, $c_i \ne d_i$), 도시 $c_i$에서 도시 $d_i$로 가는 비행 항공권을 뜻합니다.

각 테스트 케이스마다 한 줄에, 바이타자르가 원하는 여행을 만들 수 있으면 TAK을, 불가능하면 NIE를 출력하세요. 여기서 TAK은 가능함을, NIE는 불가능함을 뜻합니다.