Nič nas ne sme presenetiti!

Osnovne informacije

Omejitve
  • Čas: 3 s
  • Spomin: 128 MB
Avtor:
  • Jure Slak
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

V neki veliki, a siromašni državi je n mest, ki so povezana z najmanjšim možnim številom dvosmernih cest, tako da so vsa mesta medsebojno povezana. Veliko mest kaže separatistične težnje in vrhovni vodja se boji, da se bo nekaj mest odcepilo in ustanovilo svojo državo. Zato je svoje vojaške stratege prosil, naj pripravijo načrt "NNNP: Nič nas ne sme presenetiti!" in analizirajo različne možne scenarije razpada njegove države.

Naloga

Dane imate podatke o mestih in cestah, ter q scenarijev. Vsak scenarij je predstavljen z neko podmnožico mest, ki se lahko uprejo. Vojaški strategi so ugotovili, da se neka množica uporniških mest lahko odcepi le, če jim ne bo treba graditi novih cest (ki so zelo drage), da bi bila njihova nova država ozemeljsko celovita. Drugače povedano, po že obstoječih cestah med uporniškimi mesti mora biti možno priti od vsakega uporniškega mesta do vsakega drugega uporniškega mesta. Vaša naloga je, da jim pomagate čim hitreje analizirati vse scenarije, saj veliki vodja postaja vse bolj nestrpen, glavo pa imate (vsak izmed vas) le eno…

Vhodni podatki

V prvi vrstici sta celi števili n in q, tj. število mest in število scenarijev, ki jih je potrebno analizirati. Sledi n-1 vrstic s celima številoma a_i in b_i, ki povesta, da je med mestoma a_i in b_i dvosmerna cesta. Nato sledi q vrstic. V vsaki vrstici je najprej celo število m_j, nato pa sledi še m_j celih števil c_{j,k}, ki podajajo množico uporniških mest.

Omejitve vhodnih podatkov

  • 1 \leq n \leq 10^5
  • 1 \leq a_i, b_i, c_{j,k}, m_j \leq n
  • \sum_{j=1}^q m_j \leq 10^5

Izhodni podatki

Za vsako izmed q vrstic izpišite ALAAAARHM, če mesta lahko oblikujejo svojo državo, ali pa NASLEDNJI, če je ne morejo.

Primer

Vhod

7 3
1 2
3 2
4 2
4 7
6 5
5 4
3 1 2 3
4 1 2 3 6
1 6

Izhod

ALAAAARHM
NASLEDNJI
ALAAAARHM
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task