Khi quản lý một sở thú, đôi khi bạn muốn chuyển động vật giữa các chuồng. Bạn có thể nhận ra rằng ngựa vằn sẽ thích chuồng rộng hơn hiện do chim cánh cụt ở, còn chim cánh cụt muốn chuyển đến chuồng lạnh hơn nơi gấu túi đang sống; và gấu túi sẽ chuyển đến một chuồng trống có thể chất đầy lá bạch đàn. Vì vậy, bạn chuyển gấu túi trước để giải phóng chuồng lạnh, rồi chuyển chim cánh cụt vào đó, và cuối cùng chuyển ngựa vằn.

Bạn chuyển động vật bằng các đường hầm đặc biệt nối các chuồng — bạn không muốn chúng di chuyển ngoài trời, vừa vì nguy cơ chúng sợ hãi, vừa vì nguy cơ chúng chạy trốn và tự làm mình bị thương.

Ảnh một sở thú có một con lạc đà, một con lừa và (một phần của) một con dê.

Không may là gần đây bạn đã nhận thêm động vật, và tất cả các chuồng hiện đều đầy, khiến việc di chuyển khó hơn nhiều. Ví dụ, hãy tưởng tượng gấu túi cần chuyển đến chuồng cũ của ngựa vằn — bạn không thể chuyển bất kỳ nhóm động vật nào trước. Thay vào đó, bạn học được cách chuyển động vật cùng lúc: ngựa vằn, gấu túi và chim cánh cụt bắt đầu đi vào các đường hầm khác nhau cùng lúc và đến chuồng mới cùng lúc, do đó chúng không bao giờ gặp nhau. Lưu ý rằng bạn không thể đơn giản đổi chỗ động vật trong hai chuồng có kết nối theo cách này (vì chúng sẽ gặp nhau trong đường hầm và sợ hãi).

Vậy giờ bạn có một câu đố. Bạn có danh sách các chuồng, mỗi chuồng chứa một loại động vật; một số chuồng được nối bằng đường hầm. Bạn có thể thực hiện bao nhiêu lần tùy ý việc chọn một tập động vật và chuyển mỗi nhóm đến một chuồng kề qua đường hầm, miễn là động vật trong chuồng đó cũng được chuyển trong cùng lượt, và không đường hầm nào được dùng quá một lần trong cùng lượt. Bạn cũng đã có hình dung về cách bố trí động vật hoàn hảo. Có thể đạt được nó bằng một chuỗi lượt di chuyển không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào gồm hai số nguyên $n$ ($1 \le n \le 4 \cdot 10^5$) và $m$ ($0 \le m \le 4 \cdot 10^5$), cho biết số chuồng và số đường hầm. Tiếp theo là $n$ dòng, dòng thứ $i$ chứa hai số nguyên $b_i$ ($1 \le b_i \le 10^6$) và $e_i$ ($1 \le e \le 10^6$), cho biết loại động vật ban đầu trong chuồng $i$ và loại bạn muốn có trong chuồng $i$ sau mọi lượt di chuyển. Bạn có thể giả sử $e_1, \ldots, e_n$ là một hoán vị của $b_1, \ldots, b_n$.

Tiếp theo là $m$ dòng mô tả các đường hầm. Mỗi dòng chứa hai số nguyên $x$ và $y$ ($1 \le x < y \le n$), cho biết chuồng $x$ và $y$ được nối bằng một đường hầm hai chiều. Không có hai chuồng nào được nối bằng nhiều hơn một đường hầm.

Dữ liệu ra

Nếu có thể chuyển động vật sao cho mọi chuồng đều chứa loại động vật mong muốn, hãy in possible. Ngược lại, in impossible.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

possible

Dữ liệu vào 2

2 1
1 2
2 1
1 2

Dữ liệu ra 2

impossible

Dữ liệu vào 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

Dữ liệu ra 3

possible

Dữ liệu vào 4

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

Dữ liệu ra 4

impossible