5609 - 提高:拦截

通过次数

11

提交次数

56

时间限制 : 1 秒
内存限制 : 128 MB

在一棵树形的防线上,B节点的人需要把情报送到C节点处,C节点的人拿到情报后马上送到司令部(根节点,1是根节点),节点与相邻节点前的移动时间皆是1,在A节点的发现情报是假的,请问A节点的人能在B节点的人开始送情报时开始拦截,拦截的成功的标志是在司令部之外的结点碰到C节点的出来送情报的人,如能成功拦截输出YES,否则输出NO

输入

第一行是一个正整数T(≤ 5),表示测试数据的组数, 对于每组测试数据, 第一行是两个整数n,q(1≤ n,q ≤ 100000),分别表示节点数和询问数, 接下来n-1行,每行包含两个整数x,y(1≤ x,y ≤ n),表示x和y之间有一条边相连,保证这些边能构成一棵树, 接下来q行,每行包含三个整数A,B,C(1 ≤ A,B,C ≤ n),表示一个询问,其中A是A节点所在位置,B是B节点所在位置,C是C节点所在位置,保证B节点初始不在根节点。

输出

对于每个询问,输出一行,如果能成功拦截则输出"YES",否则输出"NO"。

样例

输入

1
7 2
1 2
2 3
3 4
4 7
1 5
1 6
3 5 6
7 5 6

输出

YES
NO