Syötteenä annetaan yhtenäinen alue tasossa: aluetta rajaa yksi monikulmio ja lisäksi siinä on monikulmion muotoisia reikiä. Tehtäväsi on selvittää, mitkä monikulmioiden kulmapisteet näkevät toisensa (eli niiden välinen jana on kokonaan tasoalueen sisällä).

Syöte

Syötteen ensimmäisellä rivillä luvut R ja N: monikulmioiden lukumäärä ja kaikkien monikulmioiden kulmapisteiden yhteismäärä. Seuraavaksi ilmoitetaan jokainen monikulmio. Monikulmio alkaa rivillä, jossa on monikulmion kulmapisteiden lukumäärä N_i, ja tämän jälkeen seuraa jokaisen kulmapisteen X- ja Y-koordinaatit, jokainen kulmapiste omalla rivillään.

Ensimmäinen monikulmio on tasoalueen ulkoraja ja loput monikulmioista ovat tasoalueen reikiä. Ensimmäinen monikulmio on suunnistettu myötäpäivään ja loput vastapäivään. Mikään monikulmioista ei leikkaa itseään tai muita monikulmioita, eivätkä mitkään kolme kulmapistettä ole samalla suoralla.

Tuloste

Ilmoita jokainen pari kulmapisteitä jotka näkevät toisensa omalla rivillään kulmapisteiden järjestyslukujen parina. Parit tulee esittää niin, että parin ensimmäinen luku on pienempi kuin toinen luku. Tulosterivit tulee järjestää ensisijaisesti rivien ensimmäisten lukujen mukaan ja toissijaisesti rivien toisten lukujen mukaan.

Rajat

• R \geq 1
• 3 \leq N \leq 4096
• N_i \geq 3
• N_1 + N_2 + \ldots + N_R = N
• Koordinaatit ovat itseisarvoltaan enintään 10^9

Mainos

Kokeile ILMAISEKSI uutta debuggaustyökalua tähän tehtävään osoitteessa http://www.cs.helsinki.fi/u/totalvit/vis/visgraph.html.

Esimerkki

Syöte:

2 7
4 
0 0
0 4
6 4
6 0
3
1 2
3 1
3 3

Tuloste:

1 2
1 4
1 5
1 6
2 3
2 5
2 7
3 4
3 6
3 7
4 6
4 7
5 6
5 7
6 7