Description

The little hamster and his buddy sugar live in an underground cave, where each node is numbered $1 \sim n$. The cave forms a tree. One day, the little hamster plans to go from his bedroom ($a$) to the dining room ($b$), while his buddy simultaneously goes from his bedroom ($c$) to the library ($d$). They both take the shortest paths. Now the little hamster wants to know whether it is possible for them to meet somewhere along the way.

The little hamster is so weak and even gets abused by Master zzq every day. Please come save him!

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of nodes in the tree and the number of queries.

The next $n - 1$ lines each contain two positive integers $u$ and $v$, indicating that there is an edge between nodes $u$ and $v$.

The next $q$ lines each contain four positive integers $a$, $b$, $c$, and $d$, representing a query as described above.

Output Format

For each query, if there exists a common point, output the uppercase letter Y; otherwise output N.

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

Y
N
Y
Y
Y

Hint

Time limit 1 s, memory limit 128 MB. Since the new judge is close to the NOIP judge in speed, please be aware of the impact of constant-factor overhead.

For 20% of the testdata, $n, q \le 200$.

For 40% of the testdata, $n, q \le 2 \times 10^3$.

For 70% of the testdata, $n, q \le 5 \times 10^4$.

For 100% of the testdata, $1 \le n, q \le 10^5$.

Translated by ChatGPT 5