Croyez-vous aux rumeurs ?

Dans une célèbre expérience de psychologie, on a montré deux lignes à des personnes et on leur a demandé laquelle était la plus longue. En réalité, à l'exception d'une seule personne, tous les autres participants étaient des complices de l'expérimentateur. Les complices ont affirmé que la ligne la plus courte était en fait la plus longue. Lorsque tout l'entourage a donné la même réponse, le véritable sujet a également affirmé que la ligne courte était la plus longue. Cette expérience a montré que les gens sont fortement influencés par leur entourage, et il en va de même pour les rumeurs.

Une rumeur commence avec des diffuseurs initiaux. Il peut y avoir plusieurs diffuseurs initiaux, et en dehors de ceux-ci, personne ne crée ou ne croit une rumeur de son propre chef.

Chaque minute, les personnes qui croient à la rumeur la propagent simultanément à tous leurs voisins. Une personne au sein d'un groupe commence à croire à la rumeur dès que plus de la moitié de ses voisins y croient.

Comme les gens n'écoutent plus d'autres versions une fois qu'ils ont commencé à croire à la rumeur, ils continuent d'y croire indéfiniment.

Déterminons le moment où chaque personne commence à croire à la rumeur.

Entrée

La première ligne contient le nombre de personnes $N$. ($1 \le N \le 200\,000$). Cela signifie qu'il y a des personnes numérotées de $1$ à $N$.

À partir de la deuxième ligne, $N$ lignes sont données. La $i$-ième ligne ($1 \le i \le N$) contient les numéros des voisins de la personne $i$, suivis d'un $0$ indiquant la fin de la ligne, le tout séparé par des espaces. Les numéros sont des entiers naturels compris entre $1$ et $N$, et il n'y a pas de doublons sur une même ligne. Personne n'est son propre voisin, les relations de voisinage sont symétriques, et le nombre total de relations de voisinage bidirectionnelles ne dépasse pas $1\,000\,000$.

La ligne suivante contient le nombre de diffuseurs initiaux $M$. ($1 \le M \le N$).

La dernière ligne contient les numéros des diffuseurs initiaux séparés par des espaces. Les numéros des diffuseurs initiaux sont distincts.

Sortie

Affichez $N$ entiers $t_1, t_2, \dots, t_N$ séparés par des espaces. $t_i$ est le temps (en minutes) auquel la personne $i$ commence à croire à la rumeur pour la première fois. Si elle ne croit jamais à la rumeur même après un temps suffisamment long, affichez $-1$. On considère que les diffuseurs initiaux commencent à croire à la rumeur à la minute $0$.

Exemples

Exemple 1

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

0 1 2 3 4 0 -1

Exemple 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

4 4 3 3 2 0 1

Remarque

Exemple 1 :

• 0 minute : Les diffuseurs initiaux (personnes 1 et 6) créent la rumeur.
• 1 minute : La personne 1 propage la rumeur aux personnes 2 et 3. La personne 2 croit à la rumeur car 1 de ses 2 voisins y croit. La personne 3 ne croit pas à la rumeur car seul 1 de ses 3 voisins y croit. La personne 6 n'a pas de voisins à qui propager la rumeur.
• 2 minutes : Les personnes 1 et 2 propagent la rumeur à la personne 3. Comme 2 personnes sur 3 parmi ses voisins y croient (ce qui représente plus de la moitié), la personne 3 commence à croire à la rumeur à partir de la 2e minute.
• 3 minutes : La personne 3 propage la rumeur à la personne 4. La personne 4 commence à y croire.
• 4 minutes : La personne 5 commence également à croire à la rumeur. La personne 7 ne croira jamais à la rumeur, même après un temps suffisamment long.