Call me, Maybe
All submissions for this problem are available.
A group of students thought of creating a different VOIP network. The network, rather than being any general graph, was a tree. Every user was assigned a unique userid. This network was hierarchical, i.e there was an admin. The parent of a user is the user connected to it on the unique path when it calls the admin. All users had a parent user except the admin.
All was working fine, until a weird problem occurred in the network. It so happened that a user was only able to call his parent user. Every user (including admin) was unable to reach any of his children. Although we can see that some users can still send a message to other users. A user u can't call the parent g of his parent p (i.e. his grandparent g) but still he can send a message to his grandparent g. u can achieve this by calling p and asking p to call g and send u's message to g.
Your task is to tell, given the userid x and userid y, whether x will be able to send a message to y.
The first line of the input contains two space separated integers N, the total number of users (including admin) in the VOIP network and Q, the number of queries.
The next line contains the userid U of the admin.
Each of the next N-1 lines contains two space separated integers x and y indicating that user x is the parent of user y.
Next in the input are the queries you need to answer. There are Q lines each containing two space separated integers x and y.
For each query output a single line containing
1 if x can send a message to y
-1 if y can send a message to x
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- 0 ≤ U ≤ N-1
- 0 ≤ x,y ≤ N-1
Input: 3 2 1 1 2 1 0 0 1 0 2 Output: 1 0
|Time Limit:||0.1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions