Problem D
Listen To Your Boss

At work, Atrebla recently became overwhelmed with orders from people all over his company and is trying to reduce his workload. He has realized that a large portion of the orders are from people who don’t have the authority to tell him what to do. By identifying such orders easily, he will be able to quickly discard them. At Atrebla’s company, all employees have one manager, except for the CEO who does not have any manager. Only the “management chain” of an employee has the authority give orders to him or her. The management chain of the CEO is defined as the empty set, and the management chain of any other employee A with manager B is defined as the set of employees consisting of B and B’s management chain. Talking to other employees in the company, Atrebla realized that many employees are facing the same issue.

Help Atrebla and other employees identify the orders they can discard.


The first line contains two integers $N$ and $M$ ($2 \leq N,M \leq 100\, 000$), the number of employees at Atrebla’s company and the number of orders. Employees are numbered from $1$ to $N$ inclusive, and employee $1$ is the CEO. Next will follow $N-1$ lines, containing the manager of employees $2$ to $N$. It is guaranteed that the CEO is in the management chain of all other employees and that an employee is never in their own management chain. This is followed by $M$ lines, one for each order, where the $i$th line contains two integers $a_ i$ and $b_ i$ ($1 \leq a_ i, b_ i \leq N$, $a_ i \neq b_ i$) meaning that employee $a_ i$ received an order from employee $b_ i$.


Output $M$ lines, one for each order, containing “Yes” if the order should be ignored and “No” otherwise.

Sample Input 1 Sample Output 1
4 3
3 1
3 2
3 4

Please log in to submit a solution to this problem

Log in