Saat mengelola kebun binatang, terkadang kamu ingin memindahkan hewan antarkandang. Kamu mungkin menyadari bahwa zebra akan menyukai kandang lebih luas yang sekarang ditempati penguin, sedangkan penguin ingin pindah ke kandang lebih dingin tempat koala tinggal; dan koala akan pindah ke kandang kosong yang dapat diisi eukaliptus. Jadi kamu memindahkan koala terlebih dahulu untuk mengosongkan kandang dingin, lalu memindahkan penguin ke sana, dan akhirnya memindahkan zebra.

Cara memindahkan hewan adalah melalui terowongan khusus yang menghubungkan kandang. Kamu tidak ingin hewan bergerak di luar, baik karena risiko mereka ketakutan maupun karena risiko mereka melarikan diri dan terluka.

Foto kebun binatang dengan seekor unta, seekor keledai, dan (sebagian dari) seekor kambing.

Sayangnya, kamu baru-baru ini memperoleh lebih banyak hewan, dan semua kandang kini penuh sehingga pemindahan jauh lebih sulit. Misalkan, misalnya, koala harus pindah ke bekas kandang zebra: kamu tidak dapat memindahkan kelompok hewan mana pun terlebih dahulu. Sebagai gantinya, kamu belajar memindahkan hewan secara bersamaan: zebra, koala, dan penguin mulai menyusuri terowongan berbeda pada saat yang sama dan tiba di kandang baru pada saat yang sama, sehingga mereka tidak pernah bertemu. Perhatikan bahwa kamu tidak bisa sekadar menukar hewan di dua kandang yang terhubung dengan cara ini (karena mereka akan bertemu di terowongan dan ketakutan).

Sekarang kamu memiliki teka-teki. Ada daftar kandang, masing-masing berisi satu jenis hewan; beberapa kandang terhubung oleh terowongan. Kamu boleh, berapa kali pun, memilih sekumpulan hewan dan memindahkan masing-masing ke kandang yang bertetangga melalui terowongan, asalkan hewan di kandang tujuan juga dipindahkan dalam langkah yang sama, dan tidak ada terowongan yang digunakan lebih dari sekali dalam langkah itu. Kamu juga memiliki gambaran penempatan hewan yang sempurna. Apakah penempatan itu bisa dicapai melalui serangkaian langkah?

Masukan

Baris pertama masukan terdiri dari dua bilangan bulat $n$ ($1 \le n \le 4 \cdot 10^5$) dan $m$ ($0 \le m \le 4 \cdot 10^5$), yang menunjukkan banyaknya kandang dan terowongan. Berikutnya ada $n$ baris, dengan baris ke-$i$ berisi dua bilangan bulat $b_i$ ($1 \le b_i \le 10^6$) dan $e_i$ ($1 \le e \le 10^6$), yang menunjukkan jenis hewan di kandang $i$ pada awalnya dan jenis hewan yang diinginkan di kandang $i$ setelah semua langkah. Kamu boleh mengasumsikan bahwa $e_1, \ldots, e_n$ adalah permutasi dari $b_1, \ldots, b_n$.

Berikutnya ada $m$ baris yang mendeskripsikan terowongan. Setiap baris berisi dua bilangan bulat $x$ dan $y$ ($1 \le x < y \le n$), yang menunjukkan bahwa kandang $x$ dan $y$ terhubung oleh terowongan dua arah. Tidak ada dua kandang yang terhubung oleh lebih dari satu terowongan.

Keluaran

Jika hewan dapat dipindahkan sehingga setiap kandang berisi jenis hewan yang diinginkan, keluarkan possible. Jika tidak, keluarkan impossible.

Contoh

Masukan 1

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

Keluaran 1

possible

Masukan 2

2 1
1 2
2 1
1 2

Keluaran 2

impossible

Masukan 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

Keluaran 3

possible

Masukan 4

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

Keluaran 4

impossible