Problem V
Gáttir

Þér finnst fyndið að hrekkja aðeins besta vin þinn með því að setja hann á reitinn $(0,0)$ á óendanlegu korti af lituðum reitum. Vinur þinn hreyfir sig svo að eilífu, eitt skref í einu, alltaf í einn af fjórum aðliggjandi reitum.

Það eru $N$ reitir á kortinu sem innihalda gátt. Þegar vinur þinn stígur inn í eina gátt, þá fjarflyst hann samstundis að handahófi í aðra gátt (sem gæti verið gáttin sem hann steig í, eða einhver önnur gátt) Ef það er gátt í reitnum $(0,0)$, þá er vinur þinn einnig fjarfluttur í byrjun þegar hann er settur á kortið.

Sem partur af hrekknum, þá langar þig að láta vin þinn halda að það séu engar gáttir á kortinu. Það eina sem vinur þinn sér er liturinn á reitnum sem hann stendur á, þannig þú vilt passa að frá sjónarhorni vinar þíns sjónarhorni, þá breytast ekki litirnir á reitunum. Þannig ef vinur þinn heldur að hann hefur farið á reit, oftar en einu sinni (t.d. ef hann fer til vinstri og svo beint aftur til hægri), þá ætti hann að sjá sama litinn og þegar hann fyrst heldur að hann kom í reitinn.

Athugaðu að þegar vinur þinn stígur á gátt mun hann sjá bæði litinn á reitnum sem hann steig á og reitinn sem hann er fjarfluttur til. Þess vegnar verðurðu að lita alla reiti með gáttum eins til að koma í veg fyrir að fjarflutningurinn sé augljós um leið.

Einföld lausn væri að nota bara einn lit fyrir alla reitina. En litir eru flottir! Þannig þú vilt nota eins marga liti og þú getur.

Skoðum sýnidæmi þar sem gáttir eru á reitunum $(1,1)$, $(1,3)$ og $(3,2)$, og vinur þinn hreyfir sig á eftirfarandi hátt: upp, hægri, niður, vinstri.

Eftir þessar hreyfingar þá heldur vinur þinn að hann er kominn aftur í reitinn $(0,0)$, en raunverulega þá gæti hann einnig verið í $(2,0)$ eða $(1,2)$. Hann er nú þegar búinn að sjá litinn í reitnum $(0,0)$ í byrjun, þannig ef hann sér annan lit núna, þá veit hann að það gætu verið gáttir. Við viljum ekki að það gerist, svo við þurfum að velja sama litinn fyrir þessa 3 reiti.

Það er engin röð aðgerða möguleg þar sem vinur þinn heldur að hann endi á reit $(0,0)$ þegar hann raunverulega enda á reit $(1,0)$, þannig að þeir reitir geta verið litaðir með öðrum lit.

Hér að neðan má sjá litun með fjórum litum fyrir sýnidæmið að ofan. Það er ekki mögulegt að nota fleiri en fjóra liti fyrir þetta sýnidæmi.

Íhugum núna annað sýnidæmi þar sem gáttirnar eru á reitum $(0,0)$, $(0,1)$, $(1,0)$, $(0,-1)$ og $(-1,0)$. Segjum að vinur þinn reyni að komast í reit $(1,3)$ með því að fara til hægri einu sinni og upp þrisvar sinnum. Einn möguleiki er að hann endi á reit $(0,0)$ ef hann er fjarfluttur á þann reit eftir hvert skref. Ef vinur þinn reynir svo að fara til baka og flyst ekki frá staðsetningu sinni þegar hann gerir það, þá endar hann á reit $(-1,-3)$. Vinur þinn mun halda að hann sé á reit $(0,0)$ í annað skiptið og mun því búast við að liturinn sé sami og áður. Þú þarft því að lita reitina $(-1,-3)$ og $(0,0)$ með sama litnum.

Athugaðu að það er ekkert sérstakt við valið á reit $(1,3)$. Þú getur sýnt fram á það sama fyrir aðra reiti sem þurfa að deila lit með $(0,0)$.

Verkefni

Reiknaðu mesta fjölda lita sem þú getur notað, þannig að vinur þinn muni ekki taka eftir því að gáttir eru til.

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $N$ - fjöldi gátta.

Næst fylgja $N$ línur, hver með tveimur heiltölum. Þar sem lína $i$ inniheldur $x_i$ og $y_i$, sem táknar að gátt er á reitnum $(x_i,y_i)$.

Úttak

Skrifaðu eina heiltölu - mesta fjölda lita sem hægt er að nota, án þess að vinur þinn taki eftir því að gáttir eru til, eða $-1$ ef þú getur notað óendanlega fjölda af litum.

Takmarkanir

• $1\le N\le {10}^5$

• $-{10}^6\le x_i,y_i\le {10}^6$ (fyrir öll $1\le i\le N$)

• Engar tvær gáttir deila sömu hnitum.

Hlutverkefni

Sýnidæmi

Fyrsta sýnidæmi lýst í lýsingu verkefnis.

Öðru sýnidæmi lýst í lýsingu verkefnis.

Fyrir þriðja sýnidæmið þá getur vinur þinn bara verið fjarfluttur í sama reit og gáttin er í, þannig það er engin leið fyrir hann að taka eftir að gáttir eru til, jafnvel þótt allir reitir hafi mismunandi liti.

3
1 1
1 3
3 2

4

5
0 0
1 0
-1 0
0 1
0 -1

1

1
1 -1

-1