路径求交(Path Intersection)

题目描述

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

输入格式

输入第一行：两个整数 $n$ 和 $q$，表示树上的结点个数和询问次数

接下来 $n-1$ 行：每行两个数 $u, v$，表示第 $i$ 条边连接 $u, v$ 两点

接下来 $q$ 行：每行四个正整数 $a, b, x, y$，分别表示询问的四个参数

输出格式

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

样例输入 #1

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

样例输出 #1

N
Y

数据范围

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

对于 100% 的数据，$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐。

测试点分布