슥삭슥삭 나무자르기

면접 대비

시간 제한4초메모리 제한1024 MB

요약

트리에서 a와 b를 잇는 경로의 간선을 모두 제거한 뒤, c와 d가 여전히 연결되어 있는지 질의마다 판별합니다.

난이도: 보통10점 중 6점
유형: 트리, DFS
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $N$ 까지 번호가 붙은 $N$ 개의 정점과 $N-1$ 개의 간선으로 이루어진 트리가 주어진다. 이 트리에 대해 다음 질문에 $Q$ 번 답해야 한다.

$a$ $b$ $c$ $d$ : 정점 $a$ 에서 $b$ 로 가는 최단 경로에 속한 모든 간선을 제거한다. 그다음 $c$ 에서 $d$ 로 가는 경로가 존재하면 YES를, 존재하지 않으면 NO를 출력한다. 따옴표는 출력하지 않는다.

질문의 결과는 다른 질문에 영향을 주지 않는다. 트리의 루트는 항상 1번 정점이며, 모든 간선은 양방향이다.

입력

입력의 첫 번째 줄에 $N$ 과 $Q$ 가 공백으로 구분되어 주어진다. ( $2\le N \le 100\,000$ ; $1 \le Q \le 300\,000$ )

두 번째 줄부터 $N-1$ 개의 줄에 걸쳐 각 줄에 간선이 잇는 두 정점의 번호 $u$ 와 $v$ 가 공백으로 구분되어 주어진다. 정점 $u$ 와 정점 $v$ 를 잇는 양방향 간선이 존재한다는 뜻이다. ( $1 \le u, v \le N$ ; $u \ne v$ )

$N+1$ 번째 줄부터 $Q$ 개의 줄에 걸쳐 질문을 나타내는 정수 $a$ , $b$ , $c$ , $d$ 가 공백으로 구분되어 주어진다. ( $1 \le a, b, c, d \le N$ )

출력

$Q$ 개의 줄에 걸쳐 질문의 답을 한 줄에 하나씩, 질문 순서대로 출력한다.

예제3

예제 1

입력

예상 출력

YES
NO
YES
YES

예제 2
입력
```
2 2
1 2
1 1 2 2
1 2 1 2
```
예상 출력
```
YES
NO
```

예제 3

입력

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

예상 출력

YES
YES
YES
YES
NO
NO