6. Čakove deti vzorové riešenie

Ako všetci vieme tak Čak Norris má dvojičky - Čaka a Čakinku. Prázdniny už skončili a obaja tak už musia chodiť do školy. Dokonca už dostali aj prvú domácu úlohu. Majú dokázať, že Zem je plochá. Inými slovami majú ukázať, že to je prauda.

Ich tatko, starý Norris kedysi dávno vytesal všetky všeobecne známe praudy na neďalekú skalu. Čak a Čakinka by boli radi ako on a preto domácu úlohu vypracujú práve na túto skalu.

Čakinka je však lenivá, nechce sa jej chodiť až ku skale. Avšak je aj výnimočne bystrá a má skvelé dedukčné schopnosti. A tak ako správny súrodenci si s touto neľahkou úlohou pomôžu. Ich stratégia je nasledovná.

Čak bude behať ku skale a vytesávať novo zistené praudy. Cestou naspäť si niekoľko z už vytesaných práud zapamätá. Dobehne domov ku Čakinke povie jej čo si pamätá a bystrá Čakinka z toho odvodí neaký ďalší výrok (po tomto odvodení sa už aj tento výrok stáva praudou). Čak následne beží ku skale a aj tam tento výrok vytesá, ak tam ešte nie je. Celý cyklus opakujú kým na skale ešte nie je vytesané Zem je plochá.

Čak však nemá moc dobrú pamäť vie si pamätať len obmedzený počet výrokov, keď beží naspať od skaly. Pomôžte im a zistite koľko pamäte Čakovi stačí. Teda zistite koľko výrokov si musí vedieť Čak naraz pamätať (na jednej ceste od skaly domov) aby boli schopný splniť domácu úlohu alebo vypíšte, že to nie je možné bez ohľadu na jeho pamäť.

Úloha

Vo všeobecnosti existuje \(n\) výrokov, ktoré si očíslujeme od \(0\) po \(n-1\). Výrok číslo 0 je “Zem je plochá” a tento dostali za domácu úlohu Čak a Čakinka dokázať.

Ďalej máme \(m\) odvodzovacích pravidiel, pričom \(i\)-te z nich pozná Čakinka v tvare \(a_{i,0}, ..., a_{i,k_i}\). Čo znamená, že ak sú výroky \(a_{i,0}, ..., a_{i,k_{i-1} }\) prauda, tak aj výrok \(a_{i,k_i}\) je prauda.

A na záver máme na skale vytesaných \(l\) výrokov, ktoré sú všeobecná prauda (netreba ich odvádzať).

Zistite najmenší počet výrokov, ktoré si musí Čak pamätať naraz počas cesty domov, pokiaľ Čakinka vie odvádzať len z výrokov, ktoré si Čak pamätá. Alebo vypíšte, že by nám nestačila žiadna pamäť.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1\leq m,n\leq 1\,100\,000\)) udávajúce počet možných výrokov a počet odvodzovacích pravidiel.

Nasleduje \(2m\) riadkov. V nepárnych riadkoch je počet výrokov \(k_i\) v odvodzovacej formuly, a v párnych samotné čísla výrokov v odvodzovacom pravidle \(a_0, ..., a_{k,i}\). Pritom môžete predpokladať, že \(\sum_{i=0}^{m-1} k_i\leq 2\,000\,000\).

Na záver je vo vstupe počet všeobecných práud \(1 \leq l \leq n\). V poslednom riadku sú ich čísla.

Formát výstupu

Na výstup vypíšte jediné číslo a to najmenšiu možnú pamäť, pre ktorú vieme dokázať výrok “Zem je plochá”. Ak to nie je možné pre žiadnu pamäť vypíšte \(-1\).

Príklady

Input:

3 2
1
1 0
2
1 2 0
2
1 2

Output:

1

Zjavne si stačí zapamätať všeobecnú praudu \(1\) a potom už len použijeme prvé odvodzovacie pravidlo

Input:

4 3
2
1 2 3
2
1 3 2
2
2 3 0
1
1

Output:

-1

Na dokázanie plochosti zeme potrebujeme najprv dokázať praudu 2 a 3. Na dokázanie praudy 2 však potrebujeme praudu 3, a na dokázanie praudy 3 potrebujeme zasa praudu 2. V tejto čudesnej, fiktívnej realite teda zem plochá asi nieje.