Zoznam úloh

6. A tento nechceš?

Biznismeni z konkurenčnej organizácie Kraksne Staré Predávame našli spôsob, ako dosiahnuť, aby si od nich každý kúpil dokonalý notebook. Ich tajomstvo je nasledovné: žiadny dokonalý notebook neexistuje.

Inak povedané, každý majiteľ notebooku, ktorý svoje zariadenie používa viac než týždeň, si je vedomý všetkých jeho nedostatkov… a so správnou porciou manipulácie sa nechá presvedčiť o tom, aby ho vymenil za iný model, ktorý žiadne z nich nemá. Nie že by ten nový notebook nemal kopu ďalších problémov – ale v tom práve spočíva tá dokonalá biznisová stratégia! Keď dokážeme presvedčiť každého vlastníka notebooku, že je ochotný vymeniť ho za akýkoľvek iný, … výsledok? Veľa peňazí!

Teda, takto by to fungovalo v dokonalom svete. V realite nie je možné presvedčiť ľudí o každej výmene modelu za model. KSP má však času dosť, takže na dosiahnutie svojich cieľov je ochotné poradiť každému človeku ľubovoľne mnoho výmen. A pokiaľ to nebude stačiť, ešte stále je tu možnosť použiť nejaký “špinavý trik” (na rozidel od všetkého spomenutého doteraz), napríklad písať fake reviews na stránky online obchodov alebo spamovať diskusné fóra, aby si ľudia mysleli, že nejaký notebook má alebo nemá kľúčové nedostatky. To je však náročné, drahé a podozrivé, preto chce KSP využívať tieto spôsoby čo najmenej.

Úloha

KSP o každom modeli notebooku vie, za ktoré iné modely sú ho jeho majitelia ochotní vymeniť. Jeho cieľom je, aby dokázalo presvedčiť majiteľa akéhokoľvek notebooku na výmenu s akýmkoľvek iným notebookom. Na to, aby dosiahlo požadovaný výsledok, môže pritom spraviť ľubovoľný počet výmen.

KSP môže využívať špinavé triky. Dôsledkom jedného triku je, že majitelia konkrétneho modelu notebooku budú ochotní vymeniť ho za iný konkrétny model. KSP chce však využiť špinavých trikov čo najmenej.

Zistite, aký najmenší počet špinavých trikov musí KSP využiť, aby bolo možné sériou výmen presvedčiť majiteľa ktoréhokoľvek modelu notebooku, nech ho vymení za akýkoľvek iný model. Teda, aby pre každý cieľový model, a ľubovoľný začiatočný model existovala postupnosť výmen, po ktorých zákazník skončí s cieľovým modelom.

Formát vstupu

Na prvom riadku vstupu sú dve čísla oddelené medzerou – $1 \leq n \leq 10^5$, počet rôznych modelov notebookov. Nasleduje $n$ riadkov s číslami oddelenými medzerami. Riadok $i$ začína počtom modelov notebookov, za ktoré sú vlastníci modelu $i$ ochotní svoj notebook vymeniť. Za ním je zoznam týchto modelov. Modely sú číslované postupne od $1$. Súčet počtov modelov v jednotlivých riadkoch nepresiahne $10^6$.

Úloha má štyri testovacie sady. V prvých troch sadách platia tieto dodatočné obmedzenia:

  • V prvej sade platí, že pokiaľ je možné majiteľa jedného modelu notebooku presvedčiť o výmene za iný model, je vždy možné rovno ho presvedčiť aj o opačnej výmene.
  • V druhej sade platí, že pokiaľ je možné majiteľa jedného notebooku presvedčiť o výmene za iný model, tak ho žiadnou postupnosťou výmen nie je možné presvedčiť o opačnej výmene (to je, samozrejme, iba počiatočný stav, úloha zostáva rovnaká).
  • V tretej sade platí, že počet modelov notebookov $n$ je najviac $1000$.

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – najmenší počet špinavých trikov, ktoré musí KSP spraviť, aby dokázalo kohokoľvek presvedčiť o výmene notebooku za akýkoľvek iný model.

Príklady

Vstup

3
2 2 3
0
1 2

Výstup

1

Majitelia prvého modelu sú ochotní vymeniť ho za ľubovoľný zo zvyšných dvoch. Tí, čo majú tretí model, sú ochotní vymeniť ho za druhý, ale nie za prvý, a tí, čo majú druhý, ho nie sú ochotní vymeniť vôbec. Stačí však jedným špinavým trikom presvedčiť majiteľov druhého modelu notebooku, že sa oplatí vymeniť ho za prvý model, a bude možné presvedčiť kohokoľvek na akúkoľvek výmenu (napríklad majiteľov tretieho modelu sa dá presvedčiť o výmene s prvým modelom tak, že sa najprv presvedčia o výmene s druhým modelom, a ten potom vymenia za prvý).

Vstup

3
1 2
1 3
1 1

Výstup

0

Vstup

5
1 3
1 3
2 4 5
0
0

Výstup

2
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty