P1035双径会深庭（cross）

【题目背景】

五环控制台恢复后，门后的光沿石壁延伸，显露出通往遗迹深处的道路。为了让分散的探索队能够在途中交换发现，Ehundategh 决定在众人出发前核对每两支队伍的行进路线。

【题目描述】

控制台留下的石刻地图中共有 $n$ 间遗室，编号为 $1\sim n$。遗室之间存在 $n-1$ 条双向通道，并且任意两间遗室之间都能够通过这些通道相互抵达。

遗迹中的岔路太多，旧地图又只恢复了这部分通道。为了避免队伍在黑暗中绕行，Ehundategh 要求每支探索队始终沿着不重复经过遗室的路线前进。由于这些通道连接了全部遗室，并且没有形成环，任意两间遗室之间都恰好存在一条这样的路线。

若一支探索队从遗室 $s$ 前往遗室 $t$，便将这条唯一的路线称为它的巡查路线。一条巡查路线包含出发的遗室、抵达的遗室以及途中经过的全部遗室。

每支队伍出发时都会带上一盏能够保存探索记录的星灯。如果两支队伍的巡查路线经过同一间遗室，它们便可以在那里交接星灯，将各自发现的道路与危险留给后来者。若两条巡查路线完全分离，这次交接便无法完成。

Ehundategh 一共需要核对 $q$ 组安排。在每组安排中，第一支探索队从遗室 $s_1$ 出发，沿巡查路线前往遗室 $t_1$，第二支探索队从遗室 $s_2$ 出发，沿巡查路线前往遗室 $t_2$。

交接的具体时刻可以由队伍自行商定，因此两支队伍的行进速度和出发时刻不作限制。Ehundategh 只想知道，两条巡查路线是否至少经过同一间遗室。

【输入格式】

从文件 $\textbf{\textit{cross.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示遗室数量与需要核对的安排数量。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，表示遗室 $u,v$ 之间存在一条双向通道。

接下来 $q$ 行，每行包含四个正整数 $s_1,t_1,s_2,t_2$，依次表示两支探索队出发与抵达的遗室。

【输出格式】

输出到文件 $\textbf{\textit{cross.out}}$ 中。

对于每组安排输出一行。若两条巡查路线至少经过同一间遗室，输出字符串 Yes，否则输出字符串 No。

【样例 1 输入】

10 227 631 241 352 462 573 683 794 5 6 7104 6 5 7114 2 6 3121 7 4 5132 3 4 7144 4 6 7155 3161 2172 3183 4194 5201 2 4 5211 3 3 5222 4 1 5

【样例 1 输出】

1No2Yes3No4No5Yes6No7No8Yes9Yes

【说明/提示】

【样例 1 解释】

在第一组测试数据的第二次安排中，第一支队伍的巡查路线为 $4,2,1,3,6$，第二支队伍的巡查路线为 $5,2,1,3,7$。两条路线共同经过遗室 $2,1,3$，因此输出 Yes。

【样例 2】

见选手目录下的 $\textbf{\textit{cross/cross2.in}}$ 和 $\textbf{\textit{cross/cross2.ans}}$。

该组样例符合测试点 $1\sim 5$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{cross/cross3.in}}$ 和 $\textbf{\textit{cross/cross3.ans}}$。

该组样例符合测试点 $6\sim 10$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{cross/cross4.in}}$ 和 $\textbf{\textit{cross/cross4.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

设 $N$ 与 $Q$ 分别表示单个测试点内所有测试数据的 $n$ 与 $q$ 之和。

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n,q\leq 10^5$，$N,Q\leq 10^5$，$1\leq s_1,t_1,s_2,t_2,u,v\leq n$。

特殊性质：所有遗室可以重新编号，使每条通道均连接编号相邻的两间遗室。