EduBrick

G. Лабиринт с односторонними коридорами

2000 мс · 256 МБ · всё или ничего

Лабиринт — дерево, но каждый коридор односторонний: по нему можно пройти только в одну сторону. Для каждого запроса (x,y)(x, y) определите, можно ли добраться из xx в yy.

Формат ввода

В первой строке nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5) — количество вершин, пронумерованных от 11 до nn. В следующих n−1n-1 строках по два числа aia_i, bib_i: коридор ведёт из aia_i в bib_i и только в эту сторону. Без учёта направлений коридоры образуют дерево.

Далее число mm (1≤m≤2⋅1051 \le m \le 2 \cdot 10^5) и mm строк с запросами (xi,yi)(x_i, y_i).

Формат вывода

Для каждого запроса выведите Yes, если пройти можно, и No иначе.

Примеры

ввод
4
1 2
3 1
4 1
6
1 2
3 2
2 3
4 2
4 3
2 1
вывод
Yes
Yes
No
Yes
No
No
ввод
2
2 1
2
1 2
2 1
вывод
No
Yes
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.