Площади и фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
lamps.in
вывод
lamps.out

В Барселоне 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