H. Зуны эрс тэс ялгаа

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$T$ сурагч Зуны хуучин сургуулийн ZPP ангид элсэх хүсэлт гаргажээ. Сургуулийн зохион байгуулах хороо тэдгээрийн хэдийг ч элсүүлж магадгүй боловч дор хаяж $t$ сурагч элссэн байх ёстой. Элссэн сурагчид дурын байдлаар 2 хэсэг болон хуваагдах ёстой (нэг хэсэг нь хоосон байж болно!).

ZPP ангийн сурагчдад $n$ ширхэг багш хичээл орно. Боловсролын салбарын хөгжлийн дагуу тэдгээр багш тус бүр нь уг 2 хэсгийн яг нэгт нь хичээл орох юм (ямар ч багш аль нэг хэсэгт нь хичээл орохгүй байж болно!). $i$-дахь багш нь дор хаяж $l_{i}$, хамгийн ихдээ $r_{i}$ сурагчтай хэсэгт ажиллахыг хүснэ (бусад тохиолдолд энэ нь хэтэрхий уйтгартай эсвэл хэтэрхий хүнд байх юм). Мөн түүнчлэн зарим хос багш нар нь бие биедээ дургүй ба ижил хэсэгт хамт ажиллаж чадахгүй юм. Нийтдээ ийм хоорондоо зөрчилтэй $m$ ширхэг хос багш байна.

Та Зуны хуучин сургуулийн ахлах багш ба маш хүнд асуудалтай тулгарчээ: Хэсэг тус болгонд хэчнээн сурагч элсүүлэх болон багш тус бүр аль хэсэгт орохыг тодорхойлно уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $t$ болон $T$ ($1 ≤ t ≤ T ≤ 10^{9}$) өгөгдөнө.

2-дахь мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n ≤ 10^{5}$, $0 ≤ m ≤ 10^{5}$) өгөгдөнө.

Дараагийн $n$ мөрийн $i$-дахь мөрөнд $l_{i}$ болон $r_{i}$ ($0 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) бүхэл тоонууд өгөгдөнө.

Дараагийн $m$ мөрөнд хоорондоо зөрчилтэй хос багш нарыг дүрсэлнэ. Эдгээр мөрүүдийн мөр болгонд хос багш нарын индексүүд болох зайгаар тусгаарлагдсан 2 бүхэл тоо өгөгдөнө. Багш нар нь 1-ээс эхлэн индексжсэн байх юм. Ямар ч багш нь өөртөө зөрчилтэй биш бөгөөд хоорондоо зөрчилтэй ямар ч хос багш нь оролтод нэгээс олон удаа өгөгдөхгүй.

Гаралт

Хэрэв хуваарилалт нь боломжтой бол эхний мөрөнд '$POSSIBLE$' (хашилтгүйгээр) гэж хэвлэнэ. 2-дахь мөрөнд $t ≤ n_{1} + n_{2} ≤ T$ шаардлагыг хангах харгалзан эхний болон 2-дахь хэсгийн сурагчдын тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n_{1}$ and $n_{2}$-г хэвлэнэ. 3-дахь мөрөнд $n$ ширхэг тэмдэгт хэвлэх ба $i$-дахь тэмдэгт нь 1 эсвэл 2 байх ба энэ нь харгалзан $i$-дахь багш эхний болон 2-дахь ангид орно гэдгийг илэрхийлэх юм. Хэрэв сурагчид болон багш нарыг хэсгүүдэд олон аргаар хуваарилаж болох бол тэдгээрийн алийг нь ч хэвлэсэн болно.

Хэрэв хайж буй хуваарилалт оршин байхгүй бол '$IMPOSSIBLE$' (хашилтгүйгээр) гэж хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
10 20
3 0
3 6
4 9
16 25
Гаралт
POSSIBLE
4 16
112
Оролт
1 10
3 3
0 10
0 10
0 10
1 2
1 3
2 3
Гаралт
IMPOSSIBLE
Сэтгэгдлүүдийг ачааллаж байна...