Linna ristmikute värvimine

문제

Ma luban, et see on viimane.

Väga Uhkes Linnas toimub kohe-kohe, umbes kuu aja pärast, Iseäranis Oluline Informaatikaolümpiaad. Et kaugetele külalistele veel rohkem muljet avaldada, otsustas linnapea lisaks tänavatele ka ristmikud ära värvida. Sest noh, miks mitte, onju?

Linn koosneb ikka veel $VV$ ristmikust ning $EE$ neid ühendavast kahesuunalisest tänavast. Ristmikud on nummerdatud $1\dots V1\; \backslash ldots\; V$. Ühtki ristmike paari ei ühenda mitu tänavat, ükski tänav ei ühenda mõnd ristmikku iseendaga ja igalt ristmikult on igale teisele võimalik mööda tänavaid jalutada.

Aga alles nüüd saate te teada, et linnatänavad on, nagu paljudes uutes planeeritud linnades, väga korrapärase struktuuriga. Kui vaatleme linna koordinaattasandil, siis:

• kõik linna ristmikud on punktid, mis on täisarvuliste koordinaatidega;
• kõik linna tänavad on sirglõigud, mis on kas koordinaattelgedega paralleelsed või moodustavad nendega 45-kraadise nurga;
• linna tänavad omavahel ei lõiku.

On 10 võimalikku värvi, mis on nummerdatud $1\dots 101\; \backslash ldots\; 10$. Linnapea millegipärast arvab, et linnas on ilgelt huvitav jalutada, kui kuskil ei ole tänavat, mis ühendaks kaht sama värviga ristmikku. Kust tal sellised ideed tulevad? Ma ka ei tea... (Kas te olete üritanud sellistele ülesannetele normaalseid tekste kirjutada?!)

Teie ülesandeks on linn nende värvidega värvida. Ühtlasi, linnaeelarve on linnapea pidevate lolluste tagajärjel üsna vilets, seega erinevate värvide arv võiks olla pigem väike.

입력

Faili esimesel real on kaks täisarvu: $VV$ ja $EE$ ($3\le V\le E\le {10}^{4}3\; \backslash le\; V\; \backslash le\; E\; \backslash le\; 10^4$). Järgmisel $VV$ real on igaühel kaks tühikutega eraldatud täisarvu $x_{i}x\_i$ ja $y_{i}y\_i$ ($0\le x_i\le 10000\; \backslash le\; x\_i\; \backslash le\; 1000$, $0\le y_i\le 10000\; \backslash le\; y\_i\; \backslash le\; 1000$) --- $ii$-nda ristmiku koordinaadid. Järgmisel $EE$ real on igaühel kaks tühikutega eraldatud täisarvu $uu$ ja $vv$ ($1\le u\le V1\; \backslash le\; u\; \backslash le\; V$, $1\le v\le V1\; \backslash le\; v\; \backslash le\; V$), mis näitavad, et ristmike $uu$ ja $vv$ vahel on tänav.

출력

Faili kirjutada $VV$ rida, $ii$-ndale reale $ii$-nda ristmiku värv (täisarv lõigust $1\dots 101\; \backslash ldots\; 10$).