warcraft

Durotan, căpetenia clanului Frostwolf, face o ultima încercare în a cuceri clanurile rivale (Orcish Horde). Conform ierarhiei Orcish, căpeteniile de clan sunt denumite warchief, în timp ce liderii triburilor dintr-un clan sunt denumiți șamani. Triburile din care fac parte căpeteniile sunt triburi dominante, iar triburile conduse de șamani sunt triburi vasale.

Pe planetă există $N$ triburi, numerotate de la $1$ la $N$. Șamanul unui trib are anumite abilități de luptă. Căpetenia unui clan este șamanul tribului său. Abilitățile de luptă cunoscute de șamani sunt numerotate de la $1$ la $M$. De-a lungul timpului între triburile aceluiași clan s-au stabilit relații de vasalitate. Dacă tribul $1$ este trib dominant al tribului vasal $2$, iar tribul $2$ are ca vasal tribul $3$, vom spune că tribul $3$ se află în zona de influență a triburilor $1$ și $2$. Triburile $1$, $2$, $3$ alcătuiesc un clan.

Puterea unei căpetenii depinde de numărul triburilor ce alcătuiesc clanul, precum și de abilitățile de luptă învățate. Căpetenia unui clan are anumite abilități de luptă, dar poate să-și însușească (învețe) și abilități de luptă unice de la șamanii triburilor clanului aflate în zona sa de influență. Prin abilități de luptă unice înțelegem abilități cunoscute doar de un singur șaman din totalitatea triburilor clanului.

Exemplu: Considerăm un clan ce are $4$ triburi: $1$ ($3$, $6$), $2$ ($1$, $2$, $4$), $3$ ($3$, $5$, $6$), $4$ ($1$, $3$, $4$). Căpetenia clanului se află la tribul $1$, el fiind considerat și șamanul tribului. Acesta are abilitățile $3$, $6$. Șamanul tribului $2$ are abilitățile $1$, $2$, $4$, șamanul tribului $3$ are abilitățile $3$, $5$, $6$, șamanul tribului $4$ are abilitățile $1$, $3$, $4$. Presupunem că tribul $4$ este vasal tribului $2$, iar triburile $2$ și $3$ sunt vasale tribului $1$. Căpetenia, la abilitățile $3$, $6$ avute deja, poate să dobândească abilitățile unice $2$, $5$ de la șamanii triburilor clanului.

Durotan invocă vechiul cod al onoarei Mak'gora, ce implică provocarea la duel a căpeteniilor de clan. Câștigă duelul dacă are un număr strict mai mare de triburi în zona sa de influență, iar la număr egal de triburi, un număr strict mai mare de abilități diferite. Triburile clanului învins se vor alătura clanului său, Durotan însușindu-și (adăugându-și) abilitățile unice ale învinsului.

Cerinţe

Fiind cunoscute pentru cele $N$ triburi abilitățile fiecărui șaman, relațiile de vasalitate între triburi, numărul de ordine al unui trib al clanului Frostwolf, să se determine:

• numărul total de clanuri
• numărul de triburi din clanul Frostwolf înainte de duel
• numărul maxim de triburi pe care Duroton le poate avea după invocarea codului Mak'gora.

Date de intrare

Fişierul de intrare warcraft.in conţine pe prima linie trei numere natural $N$, $M$, $X$ ce reprezintă $N$ - numărul de triburi, $M$ - numărul de abilități, $X$ - numărul de ordine al unui trib ce face parte din clanul lui Durotan.

Pe următoarele $N$ linii descrierea fiecărui trib: $x$, $y$, $k$, $a_1$, $a_2$, $\dots$, $a_k$ unde: tribul $x$ este vasal tribului $y$. Șamanul tribului $x$ are $k$ abilități de luptă, $a_1$, $a_2$, $\dots$, $a_k$, valori strict crescătoare.

Date de ieșire

Fişierul de intrare warcraft.out va conţine trei numere naturale $n_1$, $n_2$, $n_3$, scrise fiecare pe câte o linie, unde:

• $n_1$ reprezintă total numărul de clanuri
• $n_2$ numărul de triburi ai clanului Frostwolf înainte de duel
• $n_3$ numărul maxim de triburi ai clanului Frostwolf după ce Durotan invocă codul Mak'gora.

Restricții și precizări

• $2 \leq N \leq 1 \ 000$
• $1 \leq X \leq N$
• $1 \leq M \leq 500$
• $1 \leq k \leq M$
• Numărul de clanuri $\leq 500$
• Dacă un trib nu este vasal altui trib, atunci $y = 0$
• Durotan provoacă la duel doar căpeteniile de trib. În duel sunt folosite abilitățile cunoscute sau dobândite de căpetenie
• Pentru determinarea corectă a lui $n_1$ se acordă $20\%$ din punctaj/test. Pentru determinarea corectă a lui $n_2$ se acordă $20\%$ din punctaj/test. Pentru determinarea corectă a lui $n_3$ se acordă $60\%$ din punctaj/test.

Exemplu

warcraft.in

12 6 8
4 10 5 1 2 3 4 5
12 6 4 1 2 5 6
10 0 2 5 6
2 4 4 2 3 4 5
1 12 3 1 4 5
11 0 5 2 3 4 5 6
9 5 2 2 6
6 0 3 2 4 5
7 11 6 1 2 3 4 5 6
8 10 1 4
3 2 3 2 4 5
5 1 3 1 3 6 

warcraft.out

3
5
12

Explicație

Sunt $12$ triburi, $6$ tipuri de abilități de luptă ($1$, $2$, $3$, $4$, $5$, $6$),
Tribul lui Durotan are indicele $10$. Tribul 8 aparține clanului lui Durotan.
Tribul $1$ este vasal tribului $12$. Șamanul tribului are 3 abilități: $1$, $4$, $5$
Tribul $2$ este vasal tribului $4$. Șamanul tribului are 4 abilități: $2$, $3$, $4$, $5$
Tribul $3$ este vasal tribului $2$. Șamanul tribului are 3 abilități: $2$, $4$, $5$
Tribul $4$ este vasal tribului $10$. Șamanul tribului are 5 abilități: $1$, $2$, $3$, $4$, $5$
Tribul $5$ este vasal tribului $1$. Șamanul tribului are 5 abilități: $1$, $2$, $3$, $4$, $5$
Tribul $6$ este trib dominant (nu este vasal). Șamanul tribului are 3 abilități: $2$, $4$, $5$. s.a.m.d.

Există $3$ clanuri:

• ($2$, $3$, $4$, $8$, $10$)
• ($1$, $5$, $6$, $9$, $12$)
• ($7$, $11$).

Clanul lui Durotan are $5$ triburi în zona sa de influență. Abilitățile de luptă ale lui Durotan: $5$, $6$ la care se adaugă abilitatea unică $1$. Astfel, abilitățile folosite de Durotan în primul duel vor fi: $1$, $5$, $6$.

Al doilea clan are căpetenia în tribul $6$ și este compus din $5$ triburi. Abilitățile căpeteniei în cazul unui duel sunt: $2$, $3$, $4$, $5$. Al treilea clan are căpetenia în tribul $11$. Abilitățile căpeteniei în cazul unui duel sunt: $1$, $2$, $3$, $5$, $6$.

Durotan provoacă la duel căpetenia celui de-al treilea clan. Câștigă duelul pentru că numărul de triburi ai clanului său este mai mare. După duel, numărul de triburi ai clanului Frostwolf va fi $7$, iar abilitățile după duel ale lui Durotan vor fi: $1$, $2$, $3$, $4$, $5$, $6$.

Apoi, Durotan va provoca la duel căpetenia celui de-al doilea clan. Numărul de triburi ai clanului Frostwolf după duel este $12$