Задача №111894. Чип и Дейл в лабиринте
Чип и Дейл спешат на помощь! Но внимательные зрители знают, что помощь как правило нужна самим Чипу и Дейлу, поэтому сегодня вам надо будет сыграть роль сообразительной Гаечки. Итак, Чип и Дейл снова попали в лапы к Толстопузу. Кот очень не любит грызунов и поэтому приготовил им изощренное испытание. Он собирается поместить их в лабиринт и посмотреть смогут ли они из него выбраться. Лабиринт представляет собой дерево, в котором каждое ребро имеет одно направление. Гаечка подслушала разговор Толстопузу со своими сообщниками и теперь знает несколько возможных вариантов: в какую точку лабиринта поместят её друзей, и где будет выход. Для каждого такого варианта она хочет понять, смогут ли Чип и Дейл найти выход, или нет.
В первой строке записано число \(n\) (\(n \leq 10^5\)) - количество вершин дерева. В следующих \(n-1\) строках описаны ребра дерева. В \(i+1\)-ой строке записано номера вершин \(a_i, b_i\), означающие, что в дереве есть ребро из вершины \(a_i\) в вершину \(b_i\).
Далее на отдельной строке записано число \(m\) (\(m \leq 10^5\)) -- количество запросов. После этого идут \(m\) строк с описанием запросов, в \(n + 1 + i\)-ой строке записаны через пробел числа \(x_i\) и \(y_i\).
Для каждого запроса на отдельной строке требуется вывести Yes, если в графе есть путь между вершинами \(x_i\) и \(y_i\), и No иначе.
| input.txt | output.txt |
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 |