Metroovõrgu tsoonid

문제

Mõõdukalt Tähelepanuväärses Linnas on suur metroovõrk. Metroovõrk koosneb $NN$ jaamast, mis on nummerdatud $1,\dots ,N1,\; \backslash ldots,\; N$, ning $MM$ neid ühendavast raudteelõigust. On teada, et ükski raudteelõik ei ühenda jaama iseendaga, et ükski raudteelõikude paar ei ühenda sama jaamapaari ja et mööda neid raudteelõike on võimalik sõita igast jaamast igasse teise jaama. Iga jaama kohta on teada tema asukoht $(x;y)(x;\; y)$ koordinaattasandil, kus linna keskpunkt asub punktis $(0;0)(0;\; 0)$. Et metroojaamad asuvad maa all, võib ka juhtuda, et linnas on mitu samade koordinaatidega metroojaama, erinevatel sügavustel.

Suurtes linnades on tavaks jaotada metroovõrk tsoonideks. Sama plaan on käiku minemas ka Mõõdukalt Tähelepanuväärses Linnas. Lihtsuse mõttes otsustati jaamad jaotada tsoonidesse selle järgi, kui kaugel on nad linna keskpunktist.

Selleks joonistab planeerija linnakaardile $k-1k\; -\; 1$ ringjoont, kõik keskpunktiga $(0;0)(0;\; 0)$ ja iga järgmine eelmisest suurema raadiusega. Siis:

• 1. tsoon koosneb jaamadest, mis jäävad 1. ringjoone sisse.
• 2. tsoon koosneb jaamadest, mis jäävad 1. ringjoone peale või 1. ja 2. ringjoone vahele.
• 3. tsoon koosneb jaamadest, mis jäävad 2. ringjoone peale või 2. ja 3. ringjoone vahele.
• $\dots \backslash ldots$
• $kk$. tsoon koosneb jaamadest, mis jäävad $(k-1)(k-1)$. ringjoone peale või sellest väljapoole.

Sinu ülesanne on planeerijat aidata. Tsoonisüsteemi heaks toimimiseks on veel mõned nõuded:

• Igas tsoonis peab olema vähemalt üks jaam.
• Igast $aa$. tsooni jaamast peab olema võimalik liikuda mistahes $bb$. tsooni jaama nii, et ei läbita ühtki jaama, mille tsooni number on suurem kui $\max (a,b)\backslash max(a,\; b)$.
• Tsoonide arv peab olema maksimaalne, mille juures on veel võimalik mõlemad eelmised nõuded rahuldada.

Joonisel 1 on näitena toodud üks võimalik metroovõrgustik ja tingimustele vastav tsoonideks jaotus. Esimesse tsooni kuuluvad jaamad 1, 2 ja 3; teise tsooni kuuluvad jaamad 5, 6 ja 7 ning kolmandasse tsooni ainult jaam 4. On selge, et igas tsoonis on vähemalt üks jaam.

Samuti kehtib teine nõue. Vaatame näiteks jaamu 1 ja 6, mis asuvad vastavalt 1. ja 2. tsoonis. Näeme, et jaamast 1 on võimalik liikuda jaama 6 kasutades ainult 1. ja 2. tsooni jaamu, näiteks $1\to 5\to 61\; \backslash to\; 5\; \backslash to\; 6$ või $1\to 2\to 3\to 61\; \backslash to\; 2\; \backslash to\; 3\; \backslash to\; 6$. Samuti on näiteks jaamast 1 võimalik liikuda jaama 3, läbides ainult 1. tsooni jaamu: $1\to 2\to 31\; \backslash to\; 2\; \backslash to\; 3$.

Saab näidata, et 3 on antud metroovõrgu korral suurim võimalik tsoonide arv.

입력

Sisendi esimesel real on kaks täisarvu $NN$ ($2\le N\le 3\cdot {10}^{5}2\; \backslash le\; N\; \backslash le\; 3\; \backslash cdot\; 10^5$) ja $MM$ ($1\le M\le 3\cdot {10}^{5}1\; \backslash le\; M\; \backslash le\; 3\; \backslash cdot\; 10^5$).

Neile järgnevad $NN$ rida, mis kirjeldavad jaamade asukohti. Nendest $ii$-s rida koosneb kahest täisarvust $x_{i}x\_i$ ja $y_{i}y\_i$ ($-{10}^9\le x_i,y_i\le {10}^9-10^9\; \backslash le\; x\_i,\; y\_i\; \backslash le\; 10^9$), mis tähendavad, et jaam $ii$ asub punktis $(x_i;y_i)(x\_i;\; y\_i)$.

Neile järgnevad $MM$ rida, mis kirjeldavad jaamade vahelisi raudteelõike. Nendest $jj$-s rida koosneb kahest täisarvust $uu$ ja $vv$ ($1\le u,v\le N1\; \backslash le\; u,\; v\; \backslash le\; N$, $u\mathrm{\ne }vu\; \backslash ne\; v$), mis tähendavad, et jaamad $uu$ ja $vv$ on omavahel raudteelõiguga ühendatud.

출력

Väljundi esimesele reale väljastada $KK$ --- suurim võimalik tsoonide arv.

Teisele reale väljastada $K-1K\; -\; 1$ täisarvu $D_1,D_2,\dots ,D_{K-1}D\_1,\; D\_2,\; \backslash ldots,\; D\_\{K\; -\; 1\}$ (), mis näitavad, et:

• tsoon number 1 koosneb jaamadest, mille kaugus keskpunktist on intervallis $[0,\sqrt{D_1})\backslash left[0,\; \backslash sqrt\{D\_1\}\backslash right)$;
• tsoon number $ii$ () koosneb jaamadest, mille kaugus keskpunktist on intervallis $[\sqrt{D_{i-1}},\sqrt{D_i})\backslash left[\backslash sqrt\{D\_\{i\; -\; 1\}\},\; \backslash sqrt\{D\_i\}\backslash right)$;
• tsoon number $KK$ koosneb jaamadest, mille kaugus keskpunktist on intervallis $[\sqrt{D_{K-1}},\mathrm{\infty })\backslash left[\backslash sqrt\{D\_\{K\; -\; 1\}\},\; \backslash infty\backslash right)$.

Kui suurim võimalik tsoonide arv $K=1K\; =\; 1$, siis peab teine rida olema tühi.

Kui tsoonideks jaotamiseks on mitu võimalust, väljastada ükskõik milline neist.