Teaching Tree

All submissions for this problem are available.
There are n student coders enrolled in a college, numbered from 1 to n. They are all eager to learn. Each student is so smart that not only can he/she learn the stuff taught by others but also teach the same to anyone else who wants to learn. In this way each student in the college eventually learns the topic. The first student to study the topic is Iam Root (whose number is 1). He then teaches it to other student who eventually may teach more students and so on till everyone has learnt it. This information is given to you in the form of n  1 such teaching sessions  a b, which denotes that a has taught b the topic.
Now that the exams are over, the students are fighting over who taught whom.
So, you have been called in to resolve the disputes. There are q such queries. In each query, you are given two student numbers and have to tell who taught whom. A student a is said to have taught student b, if there is a chain of students from a to b each of whom have been taught by the previous one.
For example, if there are 4 students and 1 has taught 2, 2 has taught 3 and 2 has taught 4, then 1 has also taught 3 (indirectly via 2, the chain being 1 2 3).
It is possible that neither of the input students have taught the other, in which case print "No idea". See the output section for more clarification.
.
Input
 The first line of the input contains an integer n denoting the number of students in the college.
 The next n  1 line has two integers a and b denoting that a has taught b
 The next line contains an integer q  giving the number of queries
 The next q lines have two integers x and y denoting the student numbers of the query.
Output
 For each query, output "a has taught b" if a has taught b, or "b has taught a" if b has taught a and output "No idea" if neither is the case. Note that you have to output the actual number in the output.
Constraints
 1 ≤ n, q ≤ 10^{5}
 1 ≤ a, b, x, y ≤ n
Subtasks
Subtask #1 (20 points)
 A student has taught atmost 1 other student
Subtask #2 (25 points)
 1 ≤ n, q ≤ 1000
Subtask #3 (55 points)

No extra constraints
Example
Input: 5 1 2 3 4 2 5 2 3 6 1 2 1 3 4 2 3 5 5 1 1 4 Output: 1 taught 2 1 taught 3 2 taught 4 No idea 1 taught 5 1 taught 4
Explanation
For last query Note that 1 has taught 2 and 2 has taught 4, so 1 has taught 4 (indirectly)
Author:  balajiganapath 
Tags  balajiganapath 
Date Added:  26052016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions