#P17893. Two Spanning Trees
Two Spanning Trees
题目描述
Alice 和 Bob 各有一张包含 个顶点、 条边的简单连通无向图。简单图没有自环或重边。两张图的边都按照 编号,同一个编号对应两张图中各自的一条边,端点可以不同。
Alice 在自己的图中选择一棵生成树,并公布这棵树的所有边的编号。Bob 会直接选择自己图中具有相同编号的边。
请判断:是否存在 Alice 的一棵生成树,使得这些边的编号在 Bob 的图中不能构成生成树?你只需要判断是否存在,不需要输出这棵树。
生成树是连接全部顶点、没有环、恰好含 条边的子图。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例第一行包含两个整数 。随后 行中的第 行包含四个整数 ,分别表示 Alice 的第 条边的两个端点与 Bob 的第 条边的两个端点。顶点编号均为 到 。
输出格式
对每个测试用例输出一行。如果存在满足要求的生成树,输出 YES;否则输出 NO。
数据范围
- ;
- ;
- ;
- ,,;
- 保证两张图都没有重边并且连通;
- 一个输入文件内所有测试用例的 之和、 之和分别不超过 。
样例输入
2
2 1
1 2 1 2
4 4
1 2 1 2
2 3 2 3
3 4 1 3
1 3 3 4
样例输出
NO
YES
样例解释
第二个测试用例中,编号为 的边在 Alice 的图中构成生成树,但在 Bob 的图中构成一个三角形,且没有连接顶点 。