409684: GYM103678 G Бернард и прятки на дереве

G. Бернард и прятки на деревеограничение по времени на тест4 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Бернард и его друг решили сыграть в прятки на дереве из $$$N$$$ вершин. Дерево — это связный граф без циклов и кратных ребёр. Друг спрятался и стал ждать, когда его найдут. Но Бернард перед игрой установил $$$M$$$ датчиков в некоторые вершины.

Бернард не хочет обходить все вершины в поисках своего друга, поэтому он попробует использовать показания с установленных датчиков. Датчик в вершине $$$V$$$ покажет кратчайшее расстояние до вершины, в которой спрятался друг Бернарда.

Даже с этой информацией Бернарду оказалось не так просто определить вершины, в которых мог спрятаться его друг. Поэтому Бернард попросил вас помочь ему с этой задачей.

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

Первая строка входных данных содержит целое число $$$N$$$ $$$(1 \le N \le 5 \cdot 10^5)$$$ — количество вершин в дереве.

Cледующиe $$$N - 1$$$ строк содержат по два целых числа $$$U$$$ и $$$V$$$ $$$(1 \le U, V \le N, U \ne V)$$$, обозначающих неориентированное ребро между вершинами $$$U$$$ и $$$V$$$. Гарантируется, что данные ребра образуют дерево.

Следующая строка содержит целое число $$$M$$$ $$$(1 \le M \le N)$$$ — количество датчиков, установленных Бернардом.

Следующие $$$M$$$ строк содержат по два целых числа $$$V_i, D_i$$$ $$$(1 \le V_i \le N, 1 \le D_i \le N - 1)$$$ — вершина, в которой установлен $$$i$$$-й датчик, и расстояние до вершины, в которой спрятался друг Бернарда, соответственно. Гарантируется, что никакие два датчика не установлены в одну вершину, а также, что существует хотя бы одна вершина, удовлетворяющая условиям.

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

В первой строке выведите одно целое число — количество искомых вершин.

В следующей строке через пробел выведите номера этих вершин в возрастающем порядке.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$M=1$$$	$$$15$$$	—	Полная
$$$2$$$	$$$N \le 100$$$	$$$15$$$	$$$1$$$	Полная
$$$3$$$	$$$N \cdot M \le 10^7$$$	$$$20$$$	$$$1-2$$$	Полная
$$$4$$$	—	$$$50$$$	$$$1-3$$$	Полная

ПримерыВходные данные

5
1 2
1 3
3 4
3 5
2
1 2
3 1

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

2
4 5 

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

5
1 2
1 3
3 4
3 5
2
1 2
4 2

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

1
5