OMG P15010

Statement

¡OMG, es superfuerte! ¡Salía de la disco cuando de repente vi a Johnny con bambas negras y calcetines blancos! Es tan fuerte que ahora mismo voy a enviar un SMS a todos mis amigos. Además, sé que la primera cosa que van a hacer ellos al despertarse será enviar un SMS a todos sus amigos, etc. ¿A qué hora recibirá el propio Johnny un SMS con la noticia?

Entrada

Cada entrada contiene un único caso de pruebas. La primera línea contiene el número $n$ de personas involucradas. La persona $1$ soy yo, y la persona $n$ es Johnny. A continuación, se dan $n-1$ líneas. La $i$ -ésima de estas líneas contiene: el número $i$ , el carácter “:”, un espacio, el instante de tiempo $t_i\geq 0$ en el que se despertará la persona $i$ -ésima, dos espacios, y los números de los amigos de la persona $i$ -ésima, separados por espacios. Ninguna persona tendrá más de 25 amigos. Podría ocurrir que dos personas no fueran amigos mutuos (o sea, que $a$ fuera amigo de $b$ , pero $b$ no lo fuera de $a$ : cuando $a$ se enterara de la noticia se lo diría a $b$ , pero no al revés). Por último, siempre se tiene que $t_1=0$ .

Salida

Una línea con un único entero: el instante de tiempo en el que Johnny recibirá un SMS con la noticia. Si Johnny no llegara a enterarse nunca, escribe $-1$ .

Puntuación

Hay 10 grupos de entradas. Se obtendrán 10 puntos por cada grupo de entradas resuelto correctamente, tardando no más de 1 segundo de CPU por cada entrada del grupo. Las entradas del grupo $i$ -ésimo contendrán situaciones con no más de $3$ , $5$ , $8$ , $15$ , $30$ , $100$ , $300$ , $1000$ , $3000$ y $10000$ personas en total.

Public test cases

Input

3
1: 0  2
2: 10  1 3

Output

Input

Output

Input

6
1: 0  2 3 6
2: 134  4 5
3: 87  1 2 5
4: 98  2 3 6 
5: 99  6 3 4

Output

Input

6
1: 0  2 3
2: 134  4 5
3: 87  1 2 5
4: 98  2 3 6 
5: 99  6 3 4

Output

Input

2
1: 0

Output

-1

Input

Output

Information

Author: Omer Giménez
Language: Spanish
Official solutions: C++
User solutions: C++