BGWOW - BG and WOW Cities!!
Famous lazy boy – BG lives in country “Treepal”, this country is famous for its peculiar connections between different cities . There are N cities in the country, which are connected by N−1 bidirectional ways. Every district is reachable from others. Cities are numbered from 1 to N and city 1 is capital city. Nobody knows the city where BG belongs. He lives in an unknown city, say X. BG is not only lazy. He is inventor of different words. He calls cities as WOW city if these cities belongs to the way while going from his city X to capital city 1. That city himself doesn't belong to the way to capital city 1.
Now, you are given the Q tasks to perform, in every task you are given a particular city number (X) where BG belongs and a city number (say-Y). Your task is to answer correctly, whether city number Y is WOW city or not assuming for this case that BG belongs to city X ? If Y is WOW city assuming X as a city where BG stands then you have to print “WOW”, otherwise you have to print “NO WAY”.
Input
There is only one test case. First line begins with N, number of cities in “Treepal” and then follows N-1 lines giving the description of connection between different cities.After that Q is given, and then Q lines follows city X and Y as described above.
Constraints:
N <= 1000
Q <= min(N * (N - 1) / 2, 2000)
1 <= X, Y <= N
Output
For each query of input, print one line of output denoting the query number as “Case num: ” then print the desired output. See the sample output for more details.
Example
Input: 7 1 2 2 3 2 4 1 5 2 6 2 7 3 6 1 6 7 4 2 Output: Case 1: WOW Case 2: NO WAY Case 3: WOW
Added by: | Raihat Zaman Neloy |
Date: | 2015-09-24 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |