Lorsque vous gérez un zoo, vous souhaitez parfois déplacer les animaux entre les enclos. Vous pourriez constater que les zèbres apprécieraient l’enclos plus spacieux actuellement occupé par les manchots, tandis que les manchots voudraient rejoindre l’enclos plus froid où vivent les koalas ; les koalas iraient dans un enclos vide que l’on peut remplir d’eucalyptus. Vous déplaceriez donc d’abord les koalas pour libérer l’enclos froid, puis les manchots vers celui-ci, et enfin les zèbres.

Vous déplacez les animaux à l’aide de tunnels spéciaux reliant les enclos : vous ne voulez pas qu’ils passent par l’extérieur, tant à cause du risque qu’ils prennent peur que de celui qu’ils s’échappent et se blessent.

Une photographie d’un zoo avec un chameau, un âne et (une partie d’)une chèvre.

Malheureusement, vous avez récemment acquis davantage d’animaux, et tous les enclos sont désormais pleins, ce qui complique beaucoup les déplacements. Imaginez, par exemple, que les koalas doivent rejoindre l’ancien enclos des zèbres : aucun groupe ne peut être déplacé en premier. Vous avez plutôt appris à déplacer les animaux en même temps : les zèbres, les koalas et les manchots s’engagent simultanément dans des tunnels différents et arrivent simultanément dans leurs nouveaux enclos, sans jamais se rencontrer. Vous ne pouvez pas simplement échanger ainsi les animaux de deux enclos reliés (ils se rencontreraient dans le tunnel et prendraient peur).

Vous avez donc maintenant une énigme. Vous disposez d’une liste d’enclos contenant chacun un type d’animal ; certains sont reliés par des tunnels. Vous pouvez, autant de fois que vous le souhaitez, choisir un ensemble d’animaux et déplacer chacun vers un enclos adjacent par tunnel, à condition que l’animal de cet enclos soit lui aussi déplacé lors de la même opération et qu’aucun tunnel ne soit utilisé plus d’une fois durant cette opération. Vous avez également une vision de la disposition parfaite des animaux. Peut-on l’obtenir par une suite d’opérations ?

Entrée

La première ligne de l’entrée contient deux entiers $n$ ($1 \le n \le 4 \cdot 10^5$) et $m$ ($0 \le m \le 4 \cdot 10^5$), indiquant les nombres d’enclos et de tunnels. Suivent $n$ lignes, dont la $i$-ème contient deux entiers $b_i$ ($1 \le b_i \le 10^6$) et $e_i$ ($1 \le e \le 10^6$), indiquant le type d’animal initialement dans l’enclos $i$ et celui que vous souhaitez trouver dans l’enclos $i$ après toutes les opérations. Vous pouvez supposer que $e_1, \ldots, e_n$ est une permutation de $b_1, \ldots, b_n$.

Suivent $m$ lignes décrivant les tunnels. Chacune contient deux entiers $x$ et $y$ ($1 \le x < y \le n$), indiquant que les enclos $x$ et $y$ sont reliés par un tunnel à double sens. Aucun couple d’enclos n’est relié par plus d’un tunnel.

Sortie

S’il est possible de déplacer les animaux pour que chaque enclos contienne le type souhaité, affichez possible. Sinon, affichez impossible.

Exemples

Entrée 1

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

Sortie 1

possible

Entrée 2

2 1
1 2
2 1
1 2

Sortie 2

impossible

Entrée 3

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

Sortie 3

possible

Entrée 4

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

Sortie 4

impossible