동물원 관리

동물원을 관리할 때 동물을 우리 사이로 옮기고 싶을 때가 있다. 예를 들어 얼룩말은 지금 펭귄이 쓰는 더 넓은 우리를 좋아할 수 있고, 펭귄은 코알라가 사는 더 추운 우리로 가고 싶을 수 있다. 코알라는 유칼립투스를 채울 수 있는 빈 우리로 간다. 그래서 먼저 코알라를 옮겨 추운 우리를 비우고, 펭귄을 옮긴 다음, 마지막으로 얼룩말을 옮긴다.

동물은 우리를 잇는 특수 터널로만 이동한다. 겁을 먹거나 달아나다 다칠 수 있으므로 동물이 바깥으로 나가서는 안 된다.

이제 모든 우리가 가득 차 있어서 동물을 옮기기가 훨씬 어렵다. 예를 들어 코알라가 얼룩말의 옛 우리로 가야 한다면, 먼저 움직일 수 있는 동물이 하나도 없다. 대신 동물들을 동시에 옮긴다. 얼룩말, 코알라, 펭귄이 각자 다른 터널로 함께 출발해 새 우리에 함께 도착하므로 서로 만나지 않는다. 연결된 두 우리의 동물을 그냥 맞바꿀 수는 없다. 터널 안에서 만나 겁을 먹기 때문이다.

한 번의 이동에서 동물 집합을 골라, 각 동물을 터널로 연결된 인접한 우리로 옮길 수 있다. 단, 그 우리에 있던 동물도 같은 이동에서 함께 움직여야 한다. 같은 이동에서 한 터널을 두 번 이상 쓸 수 없다. 이런 이동을 여러 번 거쳐 원하는 배치를 만들 수 있는가?

첫 줄에 우리의 수 $n$ ($1 \le n \le 4 \cdot 10^5$)과 터널의 수 $m$ ($0 \le m \le 4 \cdot 10^5$)이 주어진다. 이어지는 $n$개 줄에는 두 정수 $b_i$ ($1 \le b_i \le 10^6$)와 $e_i$ ($1 \le e_i \le 10^6$)가 주어진다. $b_i$는 우리 $i$에 처음 있는 동물의 종류이고, $e_i$는 모든 이동이 끝난 뒤 우리 $i$에 있기를 원하는 동물의 종류이다. $e_1, \dots, e_n$은 $b_1, \dots, b_n$의 순열임이 보장된다. 이어지는 $m$개 줄에는 두 정수 $x$와 $y$ ($1 \le x < y \le n$)가 주어지며, 우리 $x$와 $y$가 양방향 터널로 연결되어 있음을 뜻한다. 두 우리를 잇는 터널은 하나를 넘지 않는다.

모든 우리에 원하는 동물이 들어가도록 동물을 옮길 수 있으면 possible을 출력한다. 그렇지 않으면 impossible을 출력한다.