eolymp
bolt
Try our new interface for solving problems
Məsələlər

Gadget Hackwrench

Gadget Hackwrench

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Chip ’n’ Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench.

So, Chip and Dale are again in the paws of Fat Cat. He doesn’t like rodents much and therefore prepared a treacherous test. He is going to put them to a labyrinth and see if they can escape from it. The labyrinth is actually built as a tree where each edge has fixed direction (by definition tree is a connected unoriented graph without cycles).

Gadget has intercepted a talk between Fat Cat and his henchmen about future tests. For each test round she knows the exact location where Chip and Dale are to be put by Fat Cat and the location of an exit. Gadget wants to compute whether they will be able to find an exit for each test.

Giriş verilənləri

The first line of input contains an integer N (1N10^5) — the number of vertices in a graph.

On the next N−1 lines of input directed arcs of the tree are given. On the (i+1)^th line integer numbers a_i and b_i are given (1a_i, b_iN) denoting an arc from vertex a_i to vertex b_i. It is guaranteed that arcs a_1, a_2, ..., a_{n-1} without orientation form a tree.

Then a string with integer number M (1M10^5) is given — the number of queries to process. Next M lines describe queries: (n+1+i)^th line contain integers x_i and y_i (1x_i, y_iN).

Çıxış verilənləri

For each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between x_iand y_i, or 'No' (without quotes) in other case.

Nümunə

Giriş verilənləri #1
4
1 2
3 1
4 1
6
1 2
3 2
2 3
4 2
4 3
2 1
Çıxış verilənləri #1
Yes
Yes
No
Yes
No
No
Mənbə ACM ICPC 2012-2013, NEERC, Moscow Subregion, Moscow, Sunday, October 21, 2012