题目描述

在管理一个动物园的时候，你有时需要在不同的动物馆之间移动动物。你可能会发现斑马会喜欢更宽敞的企鹅馆，而企鹅可能想搬到目前考拉所在的更冷的场馆里；考拉则可以搬到一个没有动物居住，但充满桉树的场馆里。因此你会先移动考拉，腾出那个更冷的场馆，然后将企鹅移到那里，最后再把斑马移过去。

你移动动物的方式是使用连接这些场馆的特殊隧道——你不希望动物在户外移动，因为这会让它们受到惊吓，并且可能会逃走并伤到他们自己。

不幸的是，你最近又收养了更多的动物，所有的动物馆现在都已经满了，这使得移动动物变得更加困难。比如说，如果你想将考拉搬到之前斑马所在的圈子里——你无法先移动任何一种动物。你反而学会了同时移动动物——将斑马、考拉和企鹅同时通过不同的隧道进行移动，并且同时到达各自的新场馆——这样它们就不会相遇。请注意，你不能仅仅交换两个相连场馆里的动物（因为它们会在隧道里相遇并受到惊吓）。

因此，现在你面临一个难题。你有一个动物馆的列表，每个场馆里都有一种动物；有些场馆通过隧道相连。你可以任意次数地选择某些动物，将它们移动到与隧道连接的另一个场馆，前提是该场馆里的动物也要作为同一次移动的一部分被移动，并且同一次移动中不能使用同一条隧道超过一次。你也有自己关于动物最佳分布的设想。请问，你是否能够通过一系列移动实现这个目标？

输入格式

第一行包含两个整数 $n$ 和 $m$（$1\le n\le 4\cdot 10^5,0\le m\le 4\cdot 10^5$），分别表示动物馆数和隧道数。然后 $n$ 行，第 $i$ 行包含两个整数 $b_i$ 和 $e_i$（$1\le b_i,e_i\le 10^6$），表示动物馆 $i$ 开始时居住的动物种类和在所有移动结束后你希望居住在动物馆 $i$ 的动物种类。你可以假设 $e_1,\ldots,e_n$ 是 $b_1,\ldots,b_n$ 的一个排列。

接下来 $m$ 行描述隧道，每行两个整数 $x$ 和 $y$（$1\le x<y\le n$），表示动物馆 $x$ 和 $y$ 之间被一条双向隧道连接。没有两个动物馆被超过一条隧道连接。

输出格式

如果可以通过一系列移动操作，使得每个动物馆都容纳希望的动物类型，则输出 possible。否则输出 impossible。

3 3
1 4
4 7
7 1
1 2
2 3
1 3

possible

2 1
1 2
2 1
1 2

impossible

5 6
10 40
20 30
30 50
40 20
50 10
1 2
2 3
1 3
3 4
3 5
4 5

possible

4 4
10 10
10 20
20 10
20 20
1 2
2 3
3 4
1 4

impossible