Problem C
Dansgólf

Dæmi um dansgólf

Hefur þú ekki séð nýja dansgólfið á dansstaðnum Vestur? Það er það heitasta í bænum um þessar mundir, og unglingarnir bíða í löngum röðum eftir að komast á gólfið til að dansa!

En þrátt fyrir mikla aðsókn undanfarið hefur reksturinn hjá Vestur ekki gengið vel, og þeir leita því að öllum mögulegum leiðum til að spara peninga. Til dæmis er nokkuð dýrt að lýsa upp dansgólfið, svo nú spá þau hvort hægt sé að slökkva á eitthvað af ljósunum. Auðvitað þarf þó að vera lýsing á öllum þeim stöðum sem fólk er að dansa á.

Dansgólfið lítur út eins og sýnt er á myndinni hér til hægri. Það samanstendur af $N$ röðum og $M$ dálkum. Hvert ljós lýsir upp heila skálínu á dansgólfinu, og hefur hvert ljós sinn eigin lit.

Vestur hefur nú beðið þig um hjálp. Þau gefa þér lista af öllum þeim reitum á dansgólfinu sem innihalda dansandi fólk, og biðja þig að finna út hver er fæsti fjöldi ljósa sem þau þurfa að hafa kveikt á þannig að það sé lýsing hjá öllum þeim sem eru að dansa.

Inntak

Fyrsta lína inniheldur þrjár heiltölur $N, M, K$, þar sem $N$ táknar fjölda raða, $M$ táknar fjölda dálka, og $K$ táknar fjölda reita þar sem fólk dansar. Síðan fylgja $K$ línur, þar sem hver lína inniheldur tvær heiltölur $x, y$, $1 \leq x \leq N$ og $1 \leq y \leq m$, sem táknar að það sé fólk dansandi á reit $(x,y)$. Enginn reitur verður gefinn upp oftar en einu sinni.

Úttak

Skrifaðu út minnsta fjölda ljósa sem þarf að hafa kveikt á svo að allir reitir sem hafa dansara séu lýstir.

Útskýring á sýnidæmi 1

Figure 1: Sýnidæmi 1

Eins og sjá má á Mynd 1 þá þarf að kveikja á tveimur ljósum til að lýsa upp alla dansara (sem eru táknaðir með rauðum deplum).

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

4 4 3
3 1
1 2
3 4

2

4 1 4
1 1
2 1
3 1
4 1

4