402436: GYM100771 I Древо пицц

I. Древо пиццограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод Вначале было слово, и слово было «пицца».

У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы появлялись не просто так – они основывались на своём предке - так постепенно появилось целое генеалогическое древо из пицц, где пиццы соединены линиями со своими предшественниками.

В пиццерии «Эль ням» работает величайший повар по имени Джордж Вкусняшков. Для него очень важно сочетание пицц, это буквально смысл его жизни. Поэтому он никогда не сделает заказ из двух пицц, если первая не является предком второй. Так как просмотр генеалогического древа перед выполнением каждого заказа занимает слишком много времени, администрация «Эль ням» решила автоматизировать данный процесс. Так как «Эль ням» просто пиццерия, здесь нет программистов, поэтому администрация просит вас помочь с решением данной проблемы.

Вам даны Q заказов на изготовление 2-ух пицц. Вам необходимо выяснить для каждого заказа, будет ли его делать Джордж Вкусняшков.

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

В первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 10⁵). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1.

Далее дано число натуральное Q (1 ≤ Q ≤ 10⁵).

Далее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N).

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

Для каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами).

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

8
1 6
1 7
6 5
6 8
6 2
8 4
8 3
7
1 7
1 3
6 4
4 3
6 5
5 6
3 7

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

YES
YES
YES
NO
YES
NO
NO

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

3
1 2
1 3
3
1 2
1 3
2 1

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

YES
YES
NO