Вы верите в слухи?

В одном известном психологическом эксперименте людям показывали две линии и просили сказать, какая из них длиннее. На самом деле, за исключением одного человека, остальные были подставными лицами, заранее проинструктированными экспериментатором. Подставные лица утверждали, что более короткая линия на самом деле длиннее. Когда все окружающие давали одинаковый ответ, настоящий испытуемый также начинал утверждать, что короткая линия длиннее. Этот эксперимент показал, что люди сильно подвержены влиянию окружающих, и со слухами происходит то же самое.

Слух начинается с первоначальных распространителей. Первоначальных распространителей может быть несколько, и никто, кроме них, не начинает верить в слух сам по себе.

Каждую минуту человек, верящий в слух, одновременно распространяет его всем своим знакомым. Человек в толпе начинает верить в слух, если как минимум половина его знакомых уже верят в него.

Поскольку с того момента, как человек поверил в слух, он перестает слушать другие мнения, однажды поверив в слух, он продолжает верить в него всегда.

Давайте выясним, в какое время каждый человек впервые начинает верить в слух.

Входные данные

В первой строке дано число людей $N$ ($1 \le N \le 200\,000$), что означает наличие людей с номерами от 1 до $N$.

Начиная со второй строки, дано $N$ строк. В $i$-й строке ($1 \le i \le N$) через пробел перечислены номера знакомых человека $i$, а в конце строки стоит $0$, обозначающий конец ввода для этого человека. Номера являются натуральными числами от 1 до $N$, повторений в одной строке нет. Человек не является знакомым самому себе, отношения знакомых не бывают односторонними, а общее количество двусторонних связей не превышает $1\,000\,000$.

В следующей строке дано количество первоначальных распространителей слуха $M$ ($1 \le M \le N$).

В последней строке через пробел перечислены номера первоначальных распространителей. Номера первоначальных распространителей не повторяются.

Выходные данные

Выведите $N$ целых чисел $t_1, t_2, \dots, t_N$ через пробел. $t_i$ — это время (в минутах), когда человек $i$ впервые начал верить в слух. Если человек не начнет верить в слух даже по прошествии достаточного количества времени, выведите $-1$. Считается, что первоначальные распространители начинают верить в слух с 0-й минуты.

Примеры

Примеры 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

Примеры 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

Примечание

В примере 1: 0 минут: Первоначальные распространители (люди 1 и 6) создают слух. 1 минута: Человек 1 распространяет слух людям 2 и 3. Человек 2 начинает верить в слух, так как 1 из 2 его знакомых верит в него. Человек 3 не верит в слух, так как только 1 из 3 его знакомых верит в него. У человека 6 нет знакомых, которым можно распространить слух. 2 минуты: Люди 1 и 2 распространяют слух человеку 3. Так как 2 из 3 знакомых (что составляет половину или более) верят в слух, человек 3 также начинает верить в него со 2-й минуты. 3 минуты: Человек 3 распространяет слух человеку 4. Человек 4 начинает верить в слух. 4 минуты: Человек 5 также начинает верить в слух. Человек 7 не верит в слух даже по прошествии достаточного времени.

Figure 1. Visualization of the rumor spreading process for Example 1.