| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 3 | 3 | 2 | 100.000% |
Mõõdukalt Tähelepanuväärses Linnas on suur metroovõrk. Metroovõrk koosneb $N$ jaamast, mis on nummerdatud $1, \ldots, N$, ning $M$ 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)$ koordinaattasandil, kus linna keskpunkt asub punktis $(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 - 1$ ringjoont, kõik keskpunktiga $(0; 0)$ ja iga järgmine eelmisest suurema raadiusega. Siis:
Sinu ülesanne on planeerijat aidata. Tsoonisüsteemi heaks toimimiseks on veel mõned nõuded:
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 6$ või $1 \to 2 \to 3 \to 6$. Samuti on näiteks jaamast 1 võimalik liikuda jaama 3, läbides ainult 1. tsooni jaamu: $1 \to 2 \to 3$.
Saab näidata, et 3 on antud metroovõrgu korral suurim võimalik tsoonide arv.
Sisendi esimesel real on kaks täisarvu $N$ ($2 \le N \le 3 \cdot 10^5$) ja $M$ ($1 \le M \le 3 \cdot 10^5$).
Neile järgnevad $N$ rida, mis kirjeldavad jaamade asukohti. Nendest $i$-s rida koosneb kahest täisarvust $x_i$ ja $y_i$ ($-10^9 \le x_i, y_i \le 10^9$), mis tähendavad, et jaam $i$ asub punktis $(x_i; y_i)$.
Neile järgnevad $M$ rida, mis kirjeldavad jaamade vahelisi raudteelõike. Nendest $j$-s rida koosneb kahest täisarvust $u$ ja $v$ ($1 \le u, v \le N$, $u \ne v$), mis tähendavad, et jaamad $u$ ja $v$ on omavahel raudteelõiguga ühendatud.
Väljundi esimesele reale väljastada $K$ --- suurim võimalik tsoonide arv.
Teisele reale väljastada $K - 1$ täisarvu $D_1, D_2, \ldots, D_{K - 1}$ ($0 < D_1 < D_2 < \cdots < D_{K - 1} \le 2 \cdot 10^{18}$), mis näitavad, et:
Kui suurim võimalik tsoonide arv $K = 1$, siis peab teine rida olema tühi.
Kui tsoonideks jaotamiseks on mitu võimalust, väljastada ükskõik milline neist.
7 8 -1 0 2 2 1 0 -6 2 -4 -3 -3 -4 0 -5 1 2 2 3 1 5 1 7 3 6 4 5 5 6 6 7
3 12 30
See näide vastab joonisel 1 toodud metroovõrgule ja tsoonideks jaotusele. Esimesse tsooni kuuluvad jaamad, mille kaugus keskpunktist on väiksem kui $\sqrt{12} \approx 3,46$. Kolmandasse tsooni kuuluvad jaamad, mille kaugus keskpunktist on vähemalt $\sqrt{30} \approx 5,48$.
Juhime tähelepanu, et tsoonideks jaotamiseks võib olla mitu võimalust. Jooniselt on selgelt näha, et kummagi tsooni piiri on võimalik pisut suurendada või vähendada. Seega võiks väljundi teine rida olla ka näiteks 16 26.
Joonis 1: Esimesele näitele vastav metroovõrgustik
4 4 2 2 -2 -2 3 -3 -3 3 1 3 3 2 1 4 4 2
1
Selles näites on võimalik vaid joonisel 2 vasakul toodud ühe tsooniga lahendus. Juhime tähelepanu, et kuna tsoone on 1, siis on väljundi teine rida tühi.
Joonisel paremal toodud tsoonideks jaotus ei ole korrektne, kuna jaamad 1 ja 2 asuvad mõlemad 1. tsoonis, kuid ei leidu teekonda $1 \leadsto 2$, mis läbiks ainult 1. tsooni jaamu.
Joonis 2: Teisele näitele vastav metroovõrgustik