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.
- 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.
- 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.
- 1 ≤ n, q ≤ 105
- 1 ≤ a, b, x, y ≤ n
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
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
For last query Note that 1 has taught 2 and 2 has taught 4, so 1 has taught 4 (indirectly)
|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|
Fetching successful submissions