Коровы со всего мира собрались на конгресс.
Всего имеется \(N\) коров. \(N-1\) пар коров дружат.
Каждая корова знает каждую через цепочку друзей.
Им было здорово вместе, но настало время расставаться, уезжая по одной.
Они хотят уезжать в таком порядке, чтоб пока остаётся не меньше двух коров,
каждая корова имела друга среди оставшихся коров. Более того, имеется
\(M\) пар коров \((a_i, b_i)\) таких, что корова \(a_i\) должна уезжать до
коровы \(b_i\). Заметим, что коровы \(a_i\) и \(b_i\) могут быть, а могут и не быть
друзьями.
Помогите коровам определить для каждой коровы, может ли она быть последней
коровой, которая уедет. Поскольку может быть так, что нельзя устроить отъезд
коров соблюдая указанные ограничения.
ФОРМАТ ВВОДА (файл gathering.in):
Строка
\(1\)содержит два разделённых пробелом целых числа
\(N\) и
\(M\).
Каждая из строки \(2 \leq i \leq N\) содержит два целых числа \(x_i\) и \(y_i\)
где \(1 \leq x_i, y_i \leq N\) и \(x_i \neq y_i\) указывающие, что коровы
\(x_i\) и \(y_i\) - друзья.
Каждая из строк \(N+1 \leq i \leq N+M\) содержит два целых числа \(a_i\) и \(b_i\)
где \(1 \leq a_i, b_i \leq N\) и \(a_i \neq b_i\) указывающие, что корова \(a_i\)
должна уехать прежде, чем корова \(b_i\).
Гарантируется, что \(1 \leq N, M \leq 10^5\).
В тестах на \(20\%\) баллов гарантируется, что \(N, M \leq 3000\).
ФОРМАТ ВЫВОДА (файл gathering.out):
Вывод должен содержать \(N\) строк, по одному целому числу \(d_i\) в каждой строке
такие что \(d_i = 1\) если корова \(i\) может оказаться последней, и \(d_i = 0\)
в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1
1 2
2 3
3 4
4 5
2 4
|
0
0
1
1
1
|