เมื่อจัดการสวนสัตว์ บางครั้งคุณต้องการย้ายสัตว์ระหว่างคอก คุณอาจพบว่าม้าลายจะชอบคอกที่กว้างกว่าซึ่งเพนกวินอยู่ในปัจจุบัน ส่วนเพนกวินอาจอยากย้ายไปคอกที่เย็นกว่าซึ่งโคอาลาอยู่ และโคอาลาจะย้ายไปคอกว่างที่สามารถใส่ยูคาลิปตัสให้เต็มได้ ดังนั้นคุณจะย้ายโคอาลาก่อนเพื่อให้คอกเย็นว่าง จากนั้นย้ายเพนกวินไปที่นั่น และสุดท้ายย้ายม้าลาย

คุณย้ายสัตว์โดยใช้อุโมงค์พิเศษที่เชื่อมคอกต่าง ๆ คุณไม่อยากให้สัตว์เดินภายนอก ทั้งเพราะเสี่ยงที่พวกมันจะตกใจ และเพราะเสี่ยงที่จะหนีไปแล้วบาดเจ็บ

ภาพสวนสัตว์ที่มีอูฐ ลา และ (ส่วนหนึ่งของ) แพะ

น่าเสียดายที่คุณเพิ่งรับสัตว์มาเพิ่ม และตอนนี้ทุกคอกเต็มแล้ว ทำให้การย้ายสัตว์ยากขึ้นมาก เช่น สมมติว่าโคอาลาต้องย้ายไปคอกเดิมของม้าลาย คุณจะย้ายสัตว์กลุ่มใดก่อนก็ไม่ได้ คุณจึงเรียนรู้ที่จะย้ายสัตว์พร้อมกัน ม้าลาย โคอาลา และเพนกวินเริ่มเดินเข้าอุโมงค์คนละเส้นพร้อมกัน และถึงคอกใหม่พร้อมกัน ทำให้ไม่พบกันเลย สังเกตว่าคุณไม่สามารถสลับสัตว์ในสองคอกที่เชื่อมกันด้วยวิธีนี้เฉย ๆ ได้ (เพราะพวกมันจะพบกันในอุโมงค์และตกใจ)

ตอนนี้คุณจึงมีปริศนา คุณมีรายการคอก แต่ละคอกมีสัตว์หนึ่งประเภทอยู่ภายใน บางคอกเชื่อมกันด้วยอุโมงค์ คุณสามารถทำได้กี่ครั้งก็ได้ โดยแต่ละครั้งเลือกสัตว์กลุ่มหนึ่งและย้ายแต่ละกลุ่มไปยังคอกที่อยู่ติดกันผ่านอุโมงค์ โดยสัตว์ในคอกปลายทางต้องถูกย้ายในคราวเดียวกันด้วย และไม่มีอุโมงค์ใดถูกใช้มากกว่าหนึ่งครั้งในการย้ายคราวเดียวกัน คุณยังมีภาพการจัดวางสัตว์ที่สมบูรณ์แบบในใจ จะทำให้เป็นเช่นนั้นด้วยการย้ายหลายครั้งได้หรือไม่?

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสองจำนวน $n$ ($1 \le n \le 4 \cdot 10^5$) และ $m$ ($0 \le m \le 4 \cdot 10^5$) ซึ่งระบุจำนวนคอกและอุโมงค์ จากนั้นมี $n$ บรรทัด บรรทัดที่ $i$ มีจำนวนเต็มสองจำนวน $b_i$ ($1 \le b_i \le 10^6$) และ $e_i$ ($1 \le e \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

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

possible

ข้อมูลนำเข้า 2

2 1
1 2
2 1
1 2

ข้อมูลส่งออก 2

impossible

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 3

possible

ข้อมูลนำเข้า 4

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

ข้อมูลส่งออก 4

impossible