막바지 공사

다가오는 축구 세계 선수권 대회 결승전이 남아프리카 공화국에서 열린다. 조직 위원회는 대회의 위상을 높이기 위해, 남아프리카 공화국에서 가장 높은 산인 마파디(Mafadi) 정상의 고원에서 결승전을 치르기로 했다. 그러나 준비 과정에서 이 거대한 행사의 물류가 심각하게 과소평가되었다.

이제 한 달도 채 남지 않았는데, 고원 위의 경기장은 완성되었지만 그곳까지 사람을 실어 나를 교통수단은 거의 없다. 지금까지는 산 곳곳에 흩어진 작은 마을들을 잇는 좁은 길들만 있을 뿐이다. 게다가 효율을 중시했던 옛 건설자들은 두 마을 사이에 아직 아무런 연결도 존재하지 않을 때에만 그 두 마을을 잇는 길을 놓았다. 따라서 길들은 어떤 순환(cycle)도 이루지 않으며, 전체적으로 하나의 숲(forest)을 이룬다.

관중의 수가 좁은 산길의 수용 능력을 훨씬 넘어서므로, 위원회는 어느 한 지점에서 산으로 접근하는 방법을 개선하기로 했다. 낡은 터널 굴착기를 확보한 위원회는 교통을 분산시킬 몇 개의 대체 경로, 즉 터널을 뚫으려 한다.

기술자들은 여러 후보 지점을 조사했다. 각 후보 지점에는 굴착기를 공수해 내려놓는 착륙장과, 굴착기를 다시 실어 보내는 이륙장이 정해져 있다. 그런데 굴착기가 매우 낡아서 암반의 자연 구조를 따라야 하므로, 정해진 방향으로만 터널을 뚫을 수 있다.

각 후보 지점에 대해, 기존 길과 새로 뚫는 터널을 이용하여 착륙장에서 이륙장까지 가는 굴착기의 경로가 존재하는지 판정하라. 이 경로는 다음을 모두 만족해야 한다.

• 각 마을을 최대 한 번만 방문한다.
• 기술자들이 반드시 필요하다고 지정한 모든 터널을 포함한다.
• 그 밖의 터널은 전혀 포함하지 않는다.

또한 각 터널은 반드시 주어진 방향으로만 지나야 한다.

입력의 첫 줄에는 테스트 케이스의 수가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $N$, $M$, $T$ ($1 \le N, M \le 100,000$, $0 \le T \le 100,000$)가 주어진다. 각각 마을의 수, 기존 길의 수, 반드시 뚫어야 하는 터널의 수를 의미한다.

둘째 줄에는 착륙장과 이륙장의 위치가 순서대로 주어진다. (착륙장과 이륙장은 서로 다르다.)

이어지는 $M$개의 줄에는 각각 두 마을 $a$, $b$ ($0 \le a, b < N$, $a \ne b$)가 주어지며, 이는 $a$와 $b$를 잇는, 양방향으로 통행 가능한 기존 길을 의미한다.

마지막으로 $T$개의 줄에는 각각 두 마을 $a$, $b$ ($0 \le a, b < N$, $a \ne b$)가 주어지며, 이는 반드시 뚫어야 하는 터널을 의미한다. 이 터널은 $a$에서 $b$ 방향으로만 뚫을 수 있다.

마을은 $0$번부터 $N-1$번까지 번호가 매겨져 있다.

각 테스트 케이스마다 한 줄을 출력한다. 주어진 제약을 만족하는 공사가 가능하면 "POSSIBLE"을, 불가능하면 "IMPOSSIBLE"을 출력한다.