В Барселоне 15 века было n площадей. Некоторые площади соединены двусторонней дорогой. Всего существует n - 1 таких дорог, причем от каждой площади можно добраться до любой другой по этим дорогам, иначе говоря — площади образуют дерево c n вершинами.
На i-й площади находится ri фонарей. Каллуму будет легче бороться с тамплиерами, если город будет более освещен. Поэтому он хочет включить на некоторых площадях фонари, причем чтобы i-я площадь была достаточно освещена, на ней должно быть включено не менее li фонарей.
Каллум называет площадь окраинной, если она соединена ровно одной дорогой с некоторой другой.
Каллум называет площадь v яркой, если существует способ включить некоторое количество фонарей на каждой из площадей, чтобы все площади были достаточно освещены, и количество горящих фонарей на пути от площади v до всех окраинных площадей неравных v, было одинаково.
Количество горящих фонарей на пути — это суммарное количество горящих фонарей на всех площадях этого пути.
Помогите Каллуму определить, какие площади являются яркими.
В первой строке находится натуральное число n — количество площадей (2 ≤ n ≤ 105).
В следующих n - 1 строках находится описание дорог между площадями: в i-й строке два натуральных числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — номера площадей, которые соединяет данная дорога.
В следующих n строках находится описание фонарей на площадях: в i-й строке два неотрицательных целых числа li и ri (0 ≤ li ≤ ri ≤ 104) — минимальное и максимальное количество фонарей, которые можно включить на i-й площади.
Гарантируется, что площади образуют дерево.
В единственной строке выведите n чисел: 1 если данная площадь является яркой, и 0 иначе.
Первая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 15, ri ≤ 1. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 21 балл.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения n ≤ 2000. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 31 балл.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 48 баллов
6
1 2
1 3
1 4
4 5
5 6
1 3
0 4
0 4
2 3
2 2
0 0
1 1 1 1 0 1
4
1 2
1 3
1 4
1 1
1 1
1 1
1 1
1 1 1 1