题目描述

给定一棵$n$个点的树，以及$q$次询问，每次询问包含四个参数$a,b,x,y$，请你求出从$a \rightarrow b$的简单路径与$x \rightarrow y$的简单路径是否存在交点。

输入格式

输入第一行：两个整数$n$和$q$，表示树上的结点个数和询问次数 接下来$n-1$行：每行两个数$u$，$v$，表示第$i$条边连接$u,v$两点 接下来$q$行：每行四个正整数$a$，$b$，$x$，$y$，分别表示询问的四个参数

输出格式

输出共$q$行：其中第$i$行表示第$i$个询问的答案，如果两简单路径有交点，则输出 Y ，否则输出 N

5 2
1 2
1 3
3 4
2 5
1 2 3 4
3 5 1 4

N
Y

数据范围

对于 $30\%$ 的数据，保证 $n\times q\leq 10^8$ 对于 $100\%$ 的数据，$1\leq n \leq 10^5$，$1\leq q \leq 10^5$