GOT - Gao on a tree


There's a tree, with each vertex assigned a number. For each query (a, b, c), you are asked whether there is a vertex on the path from a to b, which is assigned number c?

Input

There are multiple cases, end by EOF.
For each case, the first line contains n(n<=100000) and m(m<=200000), representing the number of vertexes (numbered from 1 to n) and the number of queries.
Then n integers follows, representing the number assigned to the ith vertex.
Then n-1 lines, each of which contains a edge of the tree.
Then m lines, each of which contains three integers a, b and c(c<=n),  representing a query.

 

 

Output

You should output "Find" or "NotFind" for every query on one line.
Output a blank line AFTER every case.

 

 

Example

Input:
5 5
1 2 3 4 5
1 2
1 3
3 4
3 5
2 3 4
2 4 3
2 4 5
4 5 1
4 5 3
Output:
NotFind
Find
NotFind
NotFind
Find

hide comments
mahilewets: 2017-08-16 19:24:57

C++14 Clang 4.0 is OK with DFS-recursion.
No SIGSEGV.

vladimira: 2017-02-14 08:41:45

Last edit: 2017-03-15 10:45:37
aristofanis: 2014-02-06 19:21:22

Be careful! Got AC with C++ 4.0.0-8 and for some reason the same code compiled with C++ 4.3.2 gave me SIGSEGV! I think it has to do with the maximum stack size, as I am using recursion...

Hussain Kara Fallah: 2013-05-24 05:30:32

for who solved this problem
What is the worst complexity that passes?

:D: 2013-02-14 11:05:59

I used b) per test case. Hopefully exact judge isn't used and that's not a problem.

Luke Pebody: 2013-02-14 09:22:56

What does "Output a blank line AFTER every case." mean in this case?

Is the correct output for the sample
a) "NotFind\nFind\nNotFind\nNotFind\nFind\n"
b) "NotFind\nFind\nNotFind\nNotFind\nFind\n\n"
c) "NotFind\n\nFind\n\nNotFind\n\nNotFind\n\nFind\n\n"

Or something else?

Buda IM (retired): 2012-10-06 13:01:45

0<=c<=n

[Hakuna Matata]: 2012-09-18 05:03:06

Then n integers follows, representing the number assigned to the ith vertex.!!

This integer are differents??

lxyxynt: 2012-08-18 07:00:50

I'm sorry for my mistake..The dataset has the testcase number T, and i have deleted it and all submit has rejudged.

Damian Straszak: 2012-10-05 21:31:07

getting SIGFPE on assertion "first vertex of edge" > n
Is everything OK with the input data?


Added by:lxyxynt
Date:2012-08-17
Time limit:0.602s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64