Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: treecolor.in

Rezultatų failas: treecolor.out

Jei norite pateikti savo sprendimą - prisijunkite.

Medžio dažymas

Taisyklingu grafo nudažymu vadinsime spalvų priskyrimą grafo viršūnėms taip, kad gretimos viršūnės turėtų skirtingą spalvą. Kiekvienai spalvai priskyrę teigiamą skaičių, galėsime suskaičiuoti viso grafo spalvų sumą.

Šioje užduotyje yra duotas medis (jungus grafas be ciklų). Raskite mažiausią medžio spalvų sumą, jį nuspalvinus taisyklingai.

Pradiniai duomenys

Pirmoje eilutėje yra n (1\\len\\le10000), viršūnių kiekis. Tolesnės n eilutės yra tokios formos: u\\k\\v_1\\v_2\\dots\\v_k, kur u yra viršūnės numeris, k - jos vaikų kiekis, v_i - jos vaikai (0\\leu,k,v_i<n). Viršūnės bendrų vaikų neturi.

Rezultatai

Vienoje eilutėje rašykite vieną skaičių - mažiausią duoto medžio spalvų sumą.

Pavyzdžiai

Duomenys Rezultatai 
2
0 0
1 1 0
 
3
 
8
0 3 1 2 3
1 2 4 5
2 0
3 2 6 7
4 0
5 0
6 0
7 0
 
11