RTREE - Roger and tree

Roger is a computer science student who likes connected undirected acyclic graphs, also known as trees. He especially likes solving problems about trees. Recently Roger found a piece of paper with a rooted tree with 'N' vertices drawn on it (numbered from 1 to 'N'). He also found 'Q' queries on the same piece of paper, where each query was an integer 'Sbetween 1 to 'N'. But the paper said nothing about the description of the queries. So he decided to find the longest path of each of the subtree 'S'.

Roger spent two sleepless nights trying to solve this problem efficiently. He is still trying and won't sleep until he knows the answer to each query. Write a program which answers all the queries correctly.

Input

The first line contains an integer 'N', then N-1 lines follow.

Each of the next 'N-1' line contains two integer 'U' and 'V' which means that vertex 'U' and 'V' are connected.

Next line contains an integer 'R' which denotes the root of the tree.

Next line contains another integer 'Q' which denotes the number of queries.

Each of the next 'Q' line contains an integer 'S' between (1 to N).

Output

For each query print the longest path of the subtree 'S' rooted at vertex 'R'.

Output exactly 'Q' lines, each line containing the output of the ith query.

Example

SAMPLE INPUT
3
1 2
1 3
1
2
1
2

SAMPLE OUTPUT
2
0

Constraints

1 ≤ N ≤ 10^5
1 ≤ U,V ≤ N
1 ≤ R ≤ N
1 ≤ Q ≤ 10^5
1 ≤ S ≤ N

 

Like Trees? Try the problems: RTREE2, RTREE3 as well


Added by:Rana Saha
Date:2014-08-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem (Codecracker 2014)

hide comments
2017-03-05 15:40:56
Whats the matter of 50th test???
I'm receiving Wrong Answer, plzzzzz help :'(
2017-02-22 09:23:14
I get WA on test 50th .
How can i solve it?
2016-12-21 07:09:04
silly mistake cost me 3WA..
2016-12-13 12:26:01
I'm getting Wrong Answer on 50th test case. Somebody please suggest a suitable test case

Last edit: 2016-12-14 06:04:22
2016-10-20 10:40:05
-> anni11: How can the answer be greater than int type, can you explain? :D:D
2016-08-16 12:46:19
my 15th awesome problem, not using long long gave me 2 WA. Try longest path in a tree after this.

Last edit: 2016-08-16 12:47:40
2016-05-27 13:14:07
i m getting WA on 50th test case...plz provide any tricky case @rana saha
2016-05-23 06:36:13
MY 100th awesome question.care full with the size constraints it gave me 2 runtime error (SIGSEGV).
easy dfs implementation!!
2016-05-22 08:16:43 sneh sajal
good one :)

Last edit: 2016-05-22 08:59:03
2015-08-22 17:59:40 Ankit
nice question on trees, use fast io :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.