#P17893. Two Spanning Trees

Two Spanning Trees

题目描述

Alice 和 Bob 各有一张包含 nn 个顶点、mm 条边的简单连通无向图。简单图没有自环或重边。两张图的边都按照 1,2,…,m1,2,\ldots,m 编号,同一个编号对应两张图中各自的一条边,端点可以不同。

Alice 在自己的图中选择一棵生成树,并公布这棵树的所有边的编号。Bob 会直接选择自己图中具有相同编号的边。

请判断:是否存在 Alice 的一棵生成树,使得这些边的编号在 Bob 的图中不能构成生成树?你只需要判断是否存在,不需要输出这棵树。

生成树是连接全部顶点、没有环、恰好含 n−1n-1 条边的子图。

输入格式

第一行包含整数 tt,表示测试用例数。

每个测试用例第一行包含两个整数 n,mn,m。随后 mm 行中的第 ii 行包含四个整数 uA,vA,uB,vBu_A,v_A,u_B,v_B,分别表示 Alice 的第 ii 条边的两个端点与 Bob 的第 ii 条边的两个端点。顶点编号均为 11 到 nn。

输出格式

对每个测试用例输出一行。如果存在满足要求的生成树,输出 YES;否则输出 NO。

数据范围

  • 1≤t≤25001\le t\le2500;
  • 2≤n≤50002\le n\le5000;
  • n−1≤m≤min⁡(5000,n(n−1)/2)n-1\le m\le\min(5000,n(n-1)/2);
  • 1≤uA,vA,uB,vB≤n1\le u_A,v_A,u_B,v_B\le n,uA≠vAu_A\ne v_A,uB≠vBu_B\ne v_B;
  • 保证两张图都没有重边并且连通;
  • 一个输入文件内所有测试用例的 nn 之和、mm 之和分别不超过 50005000。

样例输入

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

样例解释

第二个测试用例中,编号为 1,2,31,2,3 的边在 Alice 的图中构成生成树,但在 Bob 的图中构成一个三角形,且没有连接顶点 44。