Problem F
Umferðarljós

Möguleg lausn á sýnidæmi 1.

Þú hefur fengið starf hjá Vegagerðinni við að endurstilla umferðarljós höfuðborgarsvæðisins. Eins og skylda er í öllum ríkisstörfum verður að gera það með sem óskilvirkasta hætti.

Því mega engin tvö aðlæg umferðarljós vera á sama lit, því þá væri mögulega hægt að keyra beint í gegnum 2 ljós, og það væri náttúrulega hættulega skilvirkt!

Einnig þarf að tryggja að engir árekstrar eigi sér stað. Því þurfa hver gatnamót að hafa grænt ljós á aðra götuna og rautt ljós á hina eða gult ljós á báðar götur. Þetta gerir auðvitað ráð fyrir að fólk fylgi umferðarlögunum.

Gatnakerfi höfuðborgarsvæðisins er gefið sem $n$ línustrik þar sem engin þrjú línustrik skerast í einum punkti. Það er að segja gatnamót eru ávallt þar sem tvær götur mætast, og það mætast aldrei þrjár eða fleiri götur á sömu gatnamótunum. Einnig skerast götur mest í einum punkti.

Gefðu litaskipan á gatnamótunum sem uppfyllir skilyrðin að ofan. Tvö gatnamót teljast aðlæg ef þau liggja á sama vegi og það eru engin önnur gatnamót á milli á þeim vegi.

Inntak

Inntak byrjar á línu með einni jákvæðri heiltölu $n$, fjöldi vega. Gefið er að $n \leq 100\, 000$. Næst koma $n$ línur þar sem $i$-ta þeirra gefur $i$-ta veginn. $i$-ti vegurinn er gefinn sem fjórar heiltölur $x_1, y_1, x_2, y_2$ þar sem vegurinn liggur frá $(x_1, y_1)$ til $(x_2, y_2)$. Gefið er að $(x_1, y_1) != (x_2, y_2)$. Öll hnit eru minnst $-1\, 000\, 000$ og mest $1\, 000\, 000$.

Úttak

Prentið fyrst fjölda gatnamóta á sinni eigin línu. Svo fyrir hver gatnamót prentið eina línu. Prentið L1 L2 C1 C2 á hverja línu þar sem $L_1$ og $L_2$ eru númer veganna sem skerast. Táknar þá $C_1$ litinn á ljósunum á þeim mótum fyrir götuna $L_1$ og $C_2$ litinn á ljósunum fyrir götuna $L_2$ á þeim mótum. Hér eru $C_1$ og $C_2$ hvort tveggja eitt af stöfunum r, y eða g. Hér táknar r rautt, y gult og g grænt. Það verða aldrei fleiri en $200\, 000$ gatnamót í úttakinu.

Ef til eru mörg svör máttu skrifa út hvaða rétta svar sem er.

Stigagjöf

5
-3 1 5 -3
5 4 2 -4
-1 -1 7 3
2 3 5 -6
-3 0 10 1

10
1 5 r g
1 3 y y
3 5 g r
3 4 y y
1 2 g r
4 5 r g
2 4 y y
2 5 g r
1 4 r g
2 3 r g

7
5 4 -7 -3
5 3 -7 -2
5 1 -7 2
5 -4 -7 1
5 -3 -7 -1
5 -1 -7 4
5 5 -7 0

14
4 7 r g
2 5 r g
1 5 g r
2 4 y y
1 4 r g
3 7 g r
6 7 r g
1 2 g r
3 6 r g
1 6 y y
2 6 g r
1 3 r g
4 5 r g
2 3 y y