Коровы со всего мира собрались на конгресс. Всего имеется n коров. n − 1 пар коров дружат. Каждая корова знает каждую через цепочку друзей.

Им было здорово вместе, но настало время расставаться, уезжая по одной. Они хотят уезжать в таком порядке, чтоб пока остаётся не меньше двух коров, каждая корова имела друга среди оставшихся коров. Более того, имеется m пар коров (ai, bi) таких, что корова ai должна уезжать до коровы bi. Заметим, что коровы ai и bi могут быть, а могут и не быть друзьями.

Помогите коровам определить для каждой коровы, может ли она быть последней коровой, которая уедет. Поскольку может быть так, что нельзя устроить отъезд коров соблюдая указанные ограничения.

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

Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 105).

Каждая из строк i (2 ≤ i ≤ n) содержит два целых числа xi и yi где 1 ≤ xi, yi ≤ n и xi ≠ yi указывающие, что коровы xi и yi - друзья.

Каждая из строк n + 1 ≤ i ≤ n + m содержит два целых числа ai и bi где 1 ≤ ai, bi ≤ n и ai ≠ bi указывающие, что корова ai должна уехать прежде, чем корова bi.

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

Выведите n строк, по одному целому числу di в каждой строке такие что di = 1 если корова i может оказаться последней, и di = 0 в противном случае.