#P18355. Grotesque Team Reconstruction

Grotesque Team Reconstruction

Grotesque Team Reconstruction

输入:标准输入
输出:标准输出

题目描述

有 nn 名学生,编号为 1,2,…,n1,2,\ldots,n,其中 n≡1(mod3)n\equiv1\pmod3。给定他们之间的 mm 条组队意愿关系。每条关系连接两个不同的学生,形成一张无向图;同一对学生之间可以出现多条关系。

需要把所有学生划分到两所学校 S1,S2S_1,S_2,满足以下全部条件:

  1. 每名学生恰好属于其中一所学校,即 S1∩S2=∅S_1\cap S_2=\varnothing 且 S1∪S2={1,2,…,n}S_1\cup S_2=\{1,2,\ldots,n\}。
  2. 两所学校人数均模 33 余 22,即 ∣S1∣≡∣S2∣≡2(mod3)|S_1|\equiv|S_2|\equiv2\pmod3。
  3. 图的两个诱导子图 G[S1]G[S_1] 与 G[S2]G[S_2] 均连通。

这里,G[S]G[S] 保留顶点集合 SS,以及原图中两个端点都属于 SS 的全部边;连通路径只能经过本校学生。

请判断是否存在这样的划分。只需要回答是否存在,不需要输出划分方案。原图不一定连通,保证没有自环,允许重边。

输入格式

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

每个测试用例的第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含两个整数 u,vu,v,表示一条无向关系。

输出格式

对于每个测试用例,如果存在满足条件的划分,输出一行 Yes;否则输出一行 No。

数据范围

  • 1≤T≤1051\le T\le10^5;
  • 4≤n≤5×1054\le n\le5\times10^5,且 n≡1(mod3)n\equiv1\pmod3;
  • 0≤m≤5×1050\le m\le5\times10^5;
  • 1≤u,v≤n1\le u,v\le n,u≠vu\ne v;
  • 同一输入文件中,所有测试用例的 nn 之和不超过 5×1055\times10^5,mm 之和也不超过 5×1055\times10^5。

注意:不保证没有重边。

样例输入 1

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

样例输出 1

Yes
No
Yes
Yes
No
No

样例说明

  • 第一组可以把 {1,2}\{1,2\} 和 {3,4}\{3,4\} 分到两所学校。
  • 第二组无论怎样划分,都无法满足全部条件。
  • 第三组可以划分为 {1,4}\{1,4\} 和 {2,3}\{2,3\}。
  • 第四组可以划分为 {1,2}\{1,2\} 和 {3,4}\{3,4\}。该样例包含重边,重边是合法的。