5. Správne poradie

Život súťažného bojovníka v Ríme je náročná záležitosť. Okrem všetkých zjavných výziev, s ktorými sa každodenne stretávajú je tu aj hlboký a fundamentálny problém, kvôli ktorému to mnohí bojoví géniovia vzdávajú hneď na začiatku. Týmto problémom je príprava tesne pred súbojom.

Asi si to viete predstaviť. Musím si nasadiť zbroj. Musím si upevniť koženú čiapku. Musím sa obuť. Musím si nasadiť holenné chrániče… Ajajáj, veď som už obutý! Musím sa vyzuť a nasadiť si holenné chrániče. Ej bisťu, zabudol som na správne bojové pomaľovanie! A všetko odznova.

Uznajte, že takýmto tempom by aj vás akurát tak porazilo. Aby Rím neprichádzal o talenty, všetky významnejšie arény začali zamestnávať prípravných špecialistov. Ich úlohou je pre každého bojovníka usporiadať jeho prípravné akcie tak, aby vzájomne nekolidovali.

Úloha

V bojovníckom svete existuje \(n\) rôznych možných prípravných akcií. Každý bojovník pri príprave na boj potrebuje vykonať niektoré z nich (nie nutne všetky). Pre niektoré dvojice akcií \(A\) a \(B\) platí, že keď niekedy vykonáme \(A\), už nikdy nebudeme vedieť vykonať \(B\) (napríklad, ak si oblečieme krúžkovú košeľu, už si nemôžeme obliecť tielko, alebo ak si nasadíme chrániče predlaktí, už si nemôžeme obliecť krúžkovú košeľu). Našťastie existuje poradie, v ktorom sa dajú vykonať všetky akcie.

Dostanete zoznam spomenutých závislostí medzi akciami. Ďalej dostanete \(q\) bojovníkov, každý z nich bude chcieť vykonať nejaký zoznam akcií. Vašou úlohou bude usporiadať akcie pre každého bojovníka.

Formát vstupu

Na prvom riadku dostanete čísla \(n\), \(m\) a \(q\) (\(1 \leq n, m, q \leq 100\,000\)) – počet rôznych možných akcií, počet závislostí medzi nimi a počet bojovníkov. Akcie sú očíslované od \(1\) po \(n\).

Nasleduje \(m\) riadkov, v každom z nich dostanete dve rôzne čísla \(A_i\) a \(B_i\) (\(1 \leq A_i, B_i \leq n\)), ktoré označujú, že keď vykonáme akciu \(A_i\), už nebudeme vedieť vykonať akciu \(B_i\).

Nakoniec nasleduje \(q\) riadkov, \(i\)-ty z nich začína celým číslom \(q_i\) (\(1 \leq q_i \leq n\)) – počtom akcií \(i\)-teho bojovníka. Za týmto číslom nasleduje \(q_i\) ďalších čísel z rozsahu \(1\) až \(n\) – čísla akcií \(i\)-teho bojovníka.

Počet všetkých akcií, ktoré chcú bojovníci vykonať (súčet všetkých \(q_i\)), neprekročí \(100\,000\). Môžete predpokladať, že prípravné kroky každého bojovníka sa dajú usporiadať tak, aby nebola porušená žiadna závislosť.

Formát výstupu

Vypíšte \(q\) riadkov, v \(i\)-tom z nich \(q_i\) čísel – zoznam krokov \(i\)-teho bojovníka v poradí, v akom ich má vykonať. Ak existuje viacero možných poradí, vypíšte ľubovoľné z nich.

Príklad

Input:

5 5 3
4 3
2 4
3 1
2 1
5 4
4 1 4 3 2
2 1 4
1 5

Output:

1 3 4 2
4 1
5

Prvý bojovník má iba jedno vhodné poradie akcií. Druhý bojovník by mohol akcie vykonať aj v opačnom poradí.