Koniec kola: 11. február 2019 23:59
20 days

Ak aj Vám chýbajú veci ako napríklad názov úlohy, limity v zadaní, príklady, možnosť submitovať, rozdelenie bodov a podobné nepodstatnosti, oznámte prosím svoju nespokojnosť autorom na kubo@ksp.sk a prefix@ksp.sk. Hodobox

Krtko si na oslavu svojho novo zrekonštruovaného bytu pozval všetkých vedúcich. Kubíkovi sa byt tak páčil, že sa rozhodol kúpiť nový nábytok do Klubovne Spokojných Programátorov. Zohnal nové staré stoly, kolieskové stoličky bez koliesok aj pekné preplnené skrine. Nákup zavŕšil novým viacdielnym kobercom. Ten sa skladá z viacerých mnohouholníkových kúskov uložených tak, že na podlahe tvoria mapu.

Netrvalo dlho a na čistučkom koberci sa začali každý deň objavovať zablatené stopy, zadupaná čokoláda či škrny od kofoly. Tie treba rýchlo odstrániť, inak sa do koberca zažerú nastálo.

Kubík dostal briliantný nápad. Na strop pripevnil kameru namierenú na koberec, takže vie presnú polohu každej škvrny v momente keď sa objaví. Od vás chce program, ktorý mu povie veľkosť zašpineného kusu koberca, aby mohol objednať správne množstvo čistiacich prostriedkov.

Úloha

Na vstupe dostanete zadanú mapu koberca v podobe grafu (vrcholy so súradnicami a hrany medzi nimi) a niekoľko bodov. Vašou úlohou je pre každý bod nájsť veľkosť oblasti, v ktorej leží. Ak sa bod nachádza mimo koberca, vypíšte -1.

Pozor! Túto úlohu je treba riešiť online, čiže treba najskôr zrátať úlohu pre jeden bod a až potom načítať zo vstupu ďalší.

Formát vstupu

Na prvom riadku vstupu je číslo n - počet vrcholov, m - počet hrán a q - počet otázok. Na sleduje n riadkov obsahujúcich 2 čísla - súradnice daného vrchola. Na ďalších m riadkoch nasledujú 2 čísla - čísla vrcholov, medzi ktorými vedú hrany. Na posledných q riadkoch nasledujú 2 celé čísla - súradnice bodu z otázky.

Formát výstupu

Pre každý bod vypíšte riadok obsahujúci jedno číslo - veľkosť oblasti v ktorej sa nachádza. Ak bod neleží v žiadnej uzavretej oblasti, vypíšte -1.

Príklady

Input:

Output:

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.