Slicing Trees and Checking Paths

Interview

Time limit4sMemory limit1024 MB

Summary

Given a tree, for each query remove the edges on the path from a to b and report whether c and d are still connected.

Level: Medium6 of 10
Topics: Tree, DFS
Solved: No attempts yet

Problem

A tree with $N$ vertices numbered from $1$ to $N$ and $N-1$ edges is given. You must answer the following $Q$ queries about this tree.

$a$ $b$ $c$ $d$ : Remove every edge on the shortest path from vertex $a$ to vertex $b$ . Print YES if a path from $c$ to $d$ still exists after the removal, and NO otherwise. Do not print the backticks.

Each query does not affect the others. The root of the tree is always vertex $1$ , and every edge is bidirectional.

Input

The first line contains $N$ and $Q$ , separated by a space. ( $2\le N \le 100\,000$ ; $1 \le Q \le 300\,000$ )

From the second line onward, each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ , separated by a space. This means there is a bidirectional edge connecting vertex $u$ and vertex $v$ . ( $1 \le u, v \le N$ ; $u \ne v$ )

From line $N+1$ onward, each of the next $Q$ lines contains four integers $a$ , $b$ , $c$ , and $d$ , separated by spaces. ( $1 \le a, b, c, d \le N$ )

Output

Print $Q$ lines, one answer per query, in the same order as the queries.

Examples3

Example 1

Input

Expected output

YES
NO
YES
YES

Example 2
Input
```
2 2
1 2
1 1 2 2
1 2 1 2
```
Expected output
```
YES
NO
```

Example 3

Input

19 6
1 2
1 3
1 4
1 5
4 6
4 7
5 8
5 9
6 10
6 11
6 12
9 13
9 14
9 15
14 16
15 17
16 18
16 19
2 3 5 6
5 11 8 15
7 11 12 10
9 14 16 19
9 16 14 19
12 17 14 11

Expected output

YES
YES
YES
YES
NO
NO