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 i-th 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 (0 <= 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

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

hide comments
2024-08-30 06:37:17
AC on 7th submission using your mom ezzz

Last edit: 2024-08-30 06:40:31
2021-05-20 14:31:40
Be careful to:
There are multiple cases, end by EOF.
(0 <= c <= n)
2021-03-11 15:15:56
learn path queries on trees (Euler tour technique)
2020-06-02 22:47:07
Why 0.602 seconds? Why not just leave it at 1 second?

Last edit: 2020-06-02 23:03:15
2020-05-11 19:13:51
i got wa for not considering c=0 and cin cout can cause tle . easily solvable using HLD. :D
2020-01-29 16:00:40
good

Last edit: 2020-01-29 16:00:53
2019-08-28 10:53:05
AC in one go
2019-08-25 09:02:54
solved with HLD and offline queries, O(m*log^2n)

Last edit: 2019-08-25 11:34:03
2018-02-10 06:05:06
ez solve in one submission
2017-08-16 19:24:57
C++14 Clang 4.0 is OK with DFS-recursion.
No SIGSEGV.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.