¿Crees en los rumores?

En un famoso experimento psicológico, se pidió a las personas que observaran dos líneas y dijeran cuál era más larga. En realidad, todos menos una persona eran cómplices del experimentador. Los cómplices afirmaron que la línea más corta era, de hecho, la más larga. Al ver que todos los demás daban la misma respuesta, el verdadero sujeto de prueba también afirmó que la línea más corta era la más larga. Este experimento demostró que las personas están fuertemente influenciadas por quienes las rodean, y los rumores funcionan de la misma manera.

Un rumor comienza con los difusores iniciales. Puede haber varios difusores iniciales y, aparte de ellos, nadie crea ni cree en un rumor por sí mismo.

Cada minuto, las personas que creen en el rumor lo difunden simultáneamente a todos sus conocidos. Una persona en la multitud comienza a creer en el rumor cuando al menos la mitad de sus conocidos ya creen en él.

Dado que, desde el momento en que alguien cree en un rumor, deja de escuchar otras versiones, una vez que se cree en un rumor, se sigue creyendo en él para siempre.

En este problema, determinaremos el tiempo en el que cada persona comienza a creer en el rumor por primera vez.

Entrada

La primera línea contiene el número de personas $N$. ($1 \le N \le 200\,000$), lo que significa que hay personas numeradas del 1 al $N$.

A partir de la segunda línea, se proporcionan $N$ líneas. La línea $i$-ésima ($1 \le i \le N$) contiene los números de los conocidos de la persona $i$, seguidos de un $0$ que indica el final de la entrada para esa línea. Los números son números naturales entre $1$ y $N$, y no hay números duplicados en la misma línea. No hay casos en los que una persona sea su propio conocido o en los que la relación de conocidos sea unilateral; el número total de relaciones bidireccionales de conocidos no supera $1\,000\,000$.

La siguiente línea contiene el número de difusores iniciales del rumor, $M$. ($1 \le M \le N$).

La última línea contiene los números de los difusores iniciales separados por espacios. Los números de los difusores iniciales no están duplicados.

Salida

Imprime $N$ enteros $t_1, t_2, \dots, t_N$ separados por espacios. $t_i$ es el tiempo (en minutos) en el que la persona $i$ comienza a creer en el rumor por primera vez, o $-1$ si no cree en el rumor incluso después de que haya pasado suficiente tiempo. Se considera que los difusores iniciales comienzan a creer en el rumor desde el minuto $0$.

Ejemplos

Entrada 1

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

Salida 1

0 1 2 3 4 0 -1

Entrada 2

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

Salida 2

4 4 3 3 2 0 1

Nota

Ejemplo 1

• Minuto 0: Los difusores iniciales (personas 1 y 6) generan el rumor.
• Minuto 1: La persona 1 difunde el rumor a las personas 2 y 3. La persona 2 comienza a creer en el rumor porque 1 de sus 2 conocidos ya cree en él. La persona 3 no cree en el rumor porque solo 1 de sus 3 conocidos cree en él. La persona 6 no tiene conocidos a quienes difundir el rumor.
• Minuto 2: Las personas 1 y 2 difunden el rumor a la persona 3. Como 2 de sus 3 conocidos (más de la mitad) creen en el rumor, la persona 3 comienza a creer en él a partir del minuto 2.
• Minuto 3: La persona 3 difunde el rumor a la persona 4. La persona 4 comienza a creer en él.
• Minuto 4: La persona 5 también comienza a creer en el rumor. La persona 7 no cree en el rumor incluso después de que pase suficiente tiempo.

Figura 1. Diagrama del proceso de difusión del rumor para el Ejemplo 1