عند إدارة حديقة حيوان، تريد أحيانًا نقل الحيوانات بين الحظائر. قد تجد أن الحمير الوحشية ستستمتع بالحظيرة الأوسع التي تشغلها البطاريق حاليًا، بينما قد ترغب البطاريق في الانتقال إلى الحظيرة الأبرد التي تسكنها الكوالا حاليًا؛ وتنتقل الكوالا إلى حظيرة فارغة يمكن ملؤها بالأوكالبتوس. لذا تنقل الكوالا أولًا لإخلاء الحظيرة الأبرد، ثم تنقل البطاريق إليها، وأخيرًا تنقل الحمير الوحشية.

تنقل الحيوانات باستخدام أنفاق خاصة تربط الحظائر — لا تريد للحيوانات أن تتحرك في الخارج، بسبب خطر أن تخاف، وكذلك خطر أن تهرب وتؤذي نفسها.

صورة لحديقة حيوان فيها جمل وحمار و(جزء من) ماعز.

للأسف، حصلت مؤخرًا على حيوانات إضافية، وأصبحت كل الحظائر ممتلئة، مما يجعل نقل الحيوانات أصعب بكثير. تخيّل مثلًا أن الكوالا ستنتقل إلى حظيرة الحمير الوحشية السابقة — لا يمكنك نقل أي مجموعة أولًا. بدلًا من ذلك، تعلّمت نقل الحيوانات في الوقت نفسه: تبدأ الحمير الوحشية والكوالا والبطاريق التحرك عبر أنفاق مختلفة في الوقت نفسه، وتصل إلى حظائرها الجديدة في الوقت نفسه، ولذلك لا تلتقي أبدًا. لاحظ أنه لا يمكنك ببساطة تبديل حيوانات حظيرتين متصلتين بهذه الطريقة (لأنها ستلتقي في النفق وتخاف).

إذن لديك الآن لغز. لديك قائمة حظائر، تحتوي كل منها على نوع من الحيوانات؛ وبعض الحظائر متصلة بأنفاق. يمكنك، أي عدد من المرات، اختيار مجموعة من الحيوانات ونقل كل منها إلى حظيرة مجاورة عبر نفق، بشرط أن يُنقل الحيوان الموجود في تلك الحظيرة أيضًا ضمن الحركة نفسها، وألا يُستخدم أي نفق أكثر من مرة في الحركة نفسها. ولديك أيضًا تصوّرك للتوزيع المثالي للحيوانات. هل يمكن تحقيقه بسلسلة من الحركات؟

الإدخال

يتكون السطر الأول من الإدخال من عددين صحيحين $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