Šeštadieninė informatikos olimpiadininkų mokykla

Didžiulis potvynis užliejo Zagrebą 1964 metais. Vanduo išvertė sienas ir daugelis namų buvo visiškai sugriauta. Šis uždavinys pateikia supaprastintą miesto modelį prieš potvynį. Reikia nustatyti, kurios sienos liko stovėti atslūgus potvyniui.

Modelį sudaro koordinačių plokštumoje išdėstytos N taškų ir W sienų. Kiekviena siena jungia du taškus ir neina per jokius kitus taškus. Modelis tenkina dar šias savybes:

• Jokios dvi sienos nekerta ir neperdengia viena kitos, tačiau jos gali liestis galiniuose taškuose;
• Kiekviena siena yra lygiagreti horizontaliai ar vertikaliai koordinačių ašiai.

Pradžioje koordinačių plokštuma yra neužlieta vandens. Nuliniu laiko momentu vanduo užlieja sienų ribojamos teritorijos išorę. Praėjus lygiai vienai valandai veikiamos spaudimo griūva visos tos sienos, kurių vienoje pusėje yra vanduo, o kitoje – vandens nėra (yra oras). Tada vanduo užlieja naują sienų neberibojamą teritoriją. Dabar gali atsirasti naujų sienų, kurių vienoje pusėje vanduo, kitoje – oras. Praėjus kitai valandai, šios sienos griūva ir vanduo veržiasi toliau. Šitaip vyksta tol, kol vanduo užlieja visą plotą.

Kaip vyksta procesas, pavaizduota paveiksluose.

Parašykite programą, kuri pagal duotų N taškų koordinates ir šiuos taškus jungiančių W sienų aprašus nustatytų, kurios sienos lieka nesugriautos po potvynio.

Pradiniai duomenys

Pirmoje eilutėje įrašytas plokštumoje pažymėtų taškų skaičių skaičius N (). Tolesnėse N eilučių yra po du sveikuosius skaičius X ir Y (abu iš intervalo ) – taško koordinatės. Taškai numeruojami nuo 1 iki N pateikimo tvarka. Jokie du taškai neturi tų pačių koordinačių.

Tolesnėje eilutėje įrašytas sienų skaičius W ().

Kiekvienoje šių W eilučių yra po du skirtingus skaičius A ir B (, ), kurie reiškia, kad prieš potvynį čia buvo siena, jungianti taškus A ir B. Sienos numeruojamos nuo 1 iki N pateikimo tvarka.

Rezultatai

Pirmoje rezultatų eilutėje turi būti įrašytas potvynio nesugriautų sienų skaičius K.

Tolesnėse K eilučių nurodomi nesugriautų sienų numeriai, vienai sienai – viena eilutė. Numeriai gali būti pateikiami bet kuria tvarka.

Pavyzdys

15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6

4
6
15
16
17