Збір корів
Корови з усього світу зібралися на конгрес. Загалом є n корів, і між ними існує n − 1 пара дружніх стосунків. Кожна корова знає кожну іншу через ланцюжок друзів.
Їм було чудово разом, але настав час розставатися, від'їжджаючи по одній. Вони хочуть від'їжджати в такому порядку, щоб, поки залишається не менше двох корів, кожна корова мала друга серед тих, що залишилися. Крім того, є m пар корів (a[i], b[i]), де корова a[i] повинна від'їхати раніше, ніж корова b[i]. Зазначимо, що корови a[i] і b[i] можуть бути, а можуть і не бути друзями.
Допоможіть коровам визначити для кожної корови, чи може вона бути останньою, яка від'їде. Можливо, що не можна організувати від'їзд корів, дотримуючись зазначених обмежень.
Вхідні дані
Перший рядок містить два цілі числа n і m (1 ≤ n, m ≤ 10^5).
Кожен з рядків i (2 ≤ i ≤ n) містить два цілі числа x[i] і y[i], де 1 ≤ x[i], y[i] ≤ n і x[i] ≠ y[i], що вказують на те, що корови x[i] і y[i] є друзями.
Кожен з рядків n + 1 ≤ i ≤ n + m містить два цілі числа a[i] і b[i], де 1 ≤ a[i], b[i] ≤ n і a[i] ≠ b[i], що вказують на те, що корова a[i] повинна від'їхати раніше, ніж корова b[i].
Вихідні дані
Виведіть n рядків, по одному цілому числу d[i] в кожному рядку, де d[i] = 1, якщо корова i може бути останньою, і d[i] = 0 в протилежному випадку.