30092번 - 슥삭슥삭 나무자르기 서브태스크

$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$개 줄 각각에는 트리의 간선이 연결하는 $2$개의 정점의 번호와 $u$와 $v$가 공백으로 구분되어 주어진다. 이는 정점 $u$와 정점 $v$를 연결하는 양방향 간선이 존재한다는 의미이다. ($1 \le u, v \le N$; $u \ne v$)

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

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