Ao gerir um jardim zoológico, por vezes queres mover os animais entre recintos. Podes concluir que as zebras gostariam do recinto mais espaçoso atualmente ocupado pelos pinguins, enquanto os pinguins poderiam querer mudar-se para o recinto mais frio onde vivem os coalas; e os coalas passariam para um recinto vazio que pode ser cheio de eucalipto. Assim, moverias primeiro os coalas para libertar o recinto frio, depois os pinguins para lá e, por fim, as zebras.

Os animais são movidos através de túneis especiais que ligam os recintos — não queres que se desloquem pelo exterior, tanto pelo risco de se assustarem como pelo risco de fugirem e se magoarem.

Uma fotografia de um jardim zoológico com um camelo, um burro e (parte de) uma cabra.

Infelizmente, adquiriste mais animais recentemente e todos os recintos estão agora cheios, o que torna as mudanças muito mais difíceis. Imagina, por exemplo, que os coalas teriam de ir para o antigo recinto das zebras — não podes mover nenhum grupo primeiro. Em vez disso, aprendeste a mover os animais ao mesmo tempo: as zebras, os coalas e os pinguins começam a percorrer túneis diferentes ao mesmo tempo e chegam aos novos recintos ao mesmo tempo, pelo que nunca se encontram. Nota que não podes simplesmente trocar assim os animais de dois recintos ligados (porque se encontrariam no túnel e ficariam assustados).

Agora tens um quebra-cabeças. Tens uma lista de recintos, cada um com um tipo de animal; alguns recintos estão ligados por túneis. Podes, qualquer número de vezes, escolher um conjunto de animais e mover cada um para um recinto adjacente por túnel, desde que o animal nesse recinto também seja movido na mesma operação e nenhum túnel seja usado mais de uma vez nessa operação. Tens também a tua visão da disposição perfeita dos animais. É possível obtê-la através de uma sequência de operações?

Entrada

A primeira linha da entrada contém dois inteiros $n$ ($1 \le n \le 4 \cdot 10^5$) e $m$ ($0 \le m \le 4 \cdot 10^5$), que indicam os números de recintos e túneis. Seguem-se $n$ linhas, sendo que a $i$-ésima contém dois inteiros $b_i$ ($1 \le b_i \le 10^6$) e $e_i$ ($1 \le e \le 10^6$), que indicam o tipo de animal inicialmente no recinto $i$ e o tipo que desejas no recinto $i$ após todas as operações. Podes assumir que $e_1, \ldots, e_n$ é uma permutação de $b_1, \ldots, b_n$.

Seguem-se $m$ linhas que descrevem os túneis. Cada linha contém dois inteiros $x$ e $y$ ($1 \le x < y \le n$), indicando que os recintos $x$ e $y$ estão ligados por um túnel de dois sentidos. Não há dois recintos ligados por mais de um túnel.

Saída

Se for possível mover os animais para que cada recinto contenha o tipo desejado, escreve possible. Caso contrário, escreve impossible.

Exemplos

Entrada 1

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

Saída 1

possible

Entrada 2

2 1
1 2
2 1
1 2

Saída 2

impossible

Entrada 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

Saída 3

possible

Entrada 4

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

Saída 4

impossible