Disko

문제

Juss sai hiljuti rikkaks. Suure diskofännina otsustas ta lasta endale ehitada diskotoa. Nagu teada, on diskotoas vaja väga palju lampe värvidega mängimiseks, seega on Jussil seal $LL$ ($1\le L\le {10}^{9}1\; \backslash le\; L\; \backslash le\; 10^9$) lampi, mis on nummerdatud $1\dots L1\; \backslash ldots\; L$. Juss avastas peagi, et lampe ükshaaval sisse ja välja lülitada on väga tülikas, seega otsustas ta lasta paigaldada $MM$ ($1\le M\le {10}^{5}1\; \backslash le\; M\; \backslash le\; 10^5$) lülitit, mis on nummerdatud $1\dots M1\; \backslash ldots\; M$ ja kus lüliti $ii$ muudab nende lampide seisundit, mille numbrid on $C_i\dots D_{i}C\_i\; \backslash ldots\; D\_i$.

Ühe peo järel soovis Juss lambid välja lülitada, aga ta avastas et need on sellises imelikus seisus, et ta ei oska neid olemasolevate lülititega välja lülitada. Täpsemalt põlevad $NN$ ($1\le N\le {10}^{5}1\; \backslash le\; N\; \backslash le\; 10^5$) lampide gruppi, kus grupp $ii$ sisaldab kõiki lampe numbritega $A_i\dots B_{i}A\_i\; \backslash ldots\; B\_i$ ja iga $i>1i\; >\; 1$ korral kehtib . Kirjuta programm, mis leiab, milliseid lüliteid peaks lülitama, et kõik lambid ära kustutada.

입력

Tekstifaili esimesel real on täisarv $LL$. Teisel real on täisarv $NN$. Järgmisel $NN$ real on igaühel kaks täisarvu $A_{i}A\_i$ ja $B_{i}B\_i$. Järgmisel real on täisarv $MM$. Viimasel $MM$ real on igaühel kaks täisarvu $C_{i}C\_i$ ja $D_{i}D\_i$.

출력

Tekstifaili esimesele reale väljastada kas EI või JAH vastavalt sellele, kas lahend leidub. Kui lahend leidub, siis väljastada teisele reale $MM$ täisarvu, mis kirjeldavad strateegiat lampide väljalülitamiseks: kohal $ii$ olev arv peab olema 1, kui lülitit $ii$ tuleb lülitada, või $00$, kui ei tule. Kui lahendit ei leidu või kui programm lahendeid ei väljasta, peab faili teine rida olema tühi.