coloring

Étant donné un arbre, vous voulez le colorier avec des entiers (plus grand au sens large que 1), de sorte que deux sommets adjacents n’aient pas la même couleur et que la somme des couleurs soit minimale. Un testcase commence par le nombre n ≤ 10000 de noeuds de l’arbre qui sont numérotés de 0 à n − 1. Il y a ensuite n lignes, contenant un entier k le nombre de fils du noeud de la ième ligne puis k entiers, les fils du noeud i. Vous devez renvoyer la valeur du coloriage optimal.

Input

5
0
4 4 0 2 3
0
0
0

3
0
2 0 2
0

6
0
0
1 4
4 2 0 5 1
0
0

8
0
0
1 3
3 6 1 0
0
1 2
1 4
1 5

4
3 2 3 1
0
0
0

3
2 2 1
0
0

1
0

3
0
1 0
1 1

6
0
1 0
1 3
0
3 2 1 5
0

2
0
1 0

6
0
1 0
0
0
4 1 3 5 2
0

10
0
1 0
3 3 1 4
4 9 5 7 8
1 6
0
0
0
0
0

4
0
1 3
1 1
1 0

8
3 3 1 5
0
0
4 6 7 4 2
0
0
0
0

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

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

2
0
1 0

3
0
2 0 2
0

1
0

8
0
0
0
0
3 6 7 2
0
2 1 0
2 5 3

Télécharger l'entrée

Output

6
4
8
11
5
4
1
4
9
3
8
13
6
11
16
16
3
4
1
11

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.