Гайка Головоломкіна#3945

Гайка Головоломкіна

1 секунда

256 мегабайтів

Дуже легка

Чіп і Дейл знову в біді! Цього разу вони потрапили в пастку Товстого Кота, який вирішив перевірити їхню кмітливість у лабіринті. Лабіринт побудований у вигляді дерева, де кожне ребро має фіксований напрямок. (Нагадаємо, що дерево — це зв'язний неорієнтований граф без циклів.)

Гайка, як завжди, намагається допомогти друзям. Вона дізналася, що Товстий Кіт планує помістити Чіпа та Дейла в певну точку лабіринту і спостерігати, чи зможуть вони знайти вихід. Для кожного випробування Гайка знає початкову точку, де опиняться Чіп і Дейл, та точку виходу. Її завдання — визначити, чи зможуть вони дістатися до виходу.

Вхідні дані

Перша строка вхідних даних містить ціле число $N$ ( $1 \leq N \leq 1 0^{5}$ 1 \le N \le 10^5) — кількість вершин у графі.

Наступні $N - 1$ N-1 строк містять орієнтовані дуги дерева. На $(i + 1)$ (i+1)-й строці вказані цілі числа $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq N$ 1 \le a_i, b_i \le N), що представляють дугу від вершини $a_{i}$ a_i до вершини $b_{i}$ b_i. Гарантовано, що дуги $a_{1}, a_{2}, \dots, a_{n - 1}$ a_1, a_2, \ldots, a_{n-1} без орієнтації утворюють дерево.

Далі йде строка з цілим числом $M$ ( $1 \leq M \leq 1 0^{5}$ 1 \le M \le 10^5) — кількість запитів. Наступні $M$ строк описують запити: $(n + 1 + i)$ (n+1+i)-а строка містить цілі числа $x_{i}$ x_i та $y_{i}$ y_i ( $1 \leq x_{i}, y_{i} \leq N$ 1 \le x_i, y_i \le N).

Вихідні дані

Для кожного запиту виведіть окремий рядок з 'Yes' (без лапок), якщо існує шлях у графі від $x_{i}$ x_i до $y_{i}$ y_i, або 'No' (без лапок) в іншому випадку.

Приклади

Приклад 1