409684: GYM103678 G Бернард и прятки на дереве
Description
Бернард и его друг решили сыграть в прятки на дереве из $$$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