Корівʼячий зʼїзд#10404
Корови з усього світу зібралися на масштабний з'їзд. Є корів та n - 1 пар корів, які дружать між собою. Кожна корова знає кожну іншу корову через певний ланцюжок дружби.
Вони чудово розважились, але тепер настав час розходитися, одна за одною. Вони хочуть розійтися у такому порядку, щоб доти, доки залишається принаймні дві корови, кожна з корів, що залишилися, мала хоча б одну подругу серед тих, що залишилися. Крім того, через проблеми зі зберіганням багажу існує пар корів (a_i, b_i), таких що корова a_i повинна піти раніше за корову b_i. Зауважте, що корови a_i та b_i можуть бути подругами, а можуть і не бути.
Для кожної корови допоможіть коровам визначити, чи може вона піти останньою. Можливо, що не існує такого порядку виходу, який задовольняє всі наведені вище обмеження.
Перший рядок містить два цілих числа та m~(1 \le n, m \le 10^5).
Кожен з наступних n - 1 рядків містить два цілих числа x_i та y_i~(1 \le x_i, y_i \le n, x_i \ne y_i), що означає, що корови x_i та y_i є подругами.
Кожен з наступних рядків містить два цілих числа a_i та b_i~(1 \le a_i, b_i \le n, a_i \ne b_i), що означає, що корова a_i повинна піти зі з'їзду раніше за корову b_i.
Виведіть рядків. У -му рядку має бути надруковано , якщо корова може піти останньою, і в іншому випадку.
Приклад 1