Un grafo no dirigido y conexo tiene \(n\) nodos, numerados de \(0\) a \(n - 1\). Encuentra el largo (en aristas) del camino más corto que visita todos los nodos. Puedes empezar y terminar en cualquier nodo, repetir nodos y usar una arista varias veces.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 12)\). La línea \(i + 1\) describe los vecinos del nodo \(i\): primero su cantidad y luego los vecinos. El grafo no tiene lazos ni aristas repetidas.

Salida

El largo del camino más corto.

Ejemplo 1

Entrada

4
3 1 2 3
1 0
1 0
1 0

Salida

4

Ejemplo 2

Entrada

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

Salida

4

Ejemplo 3

Entrada

1
0

Salida

0