#P18355. Grotesque Team Reconstruction
Grotesque Team Reconstruction
Grotesque Team Reconstruction
输入:标准输入
输出:标准输出
题目描述
有 名学生,编号为 ,其中 。给定他们之间的 条组队意愿关系。每条关系连接两个不同的学生,形成一张无向图;同一对学生之间可以出现多条关系。
需要把所有学生划分到两所学校 ,满足以下全部条件:
- 每名学生恰好属于其中一所学校,即 且 。
- 两所学校人数均模 余 ,即 。
- 图的两个诱导子图 与 均连通。
这里, 保留顶点集合 ,以及原图中两个端点都属于 的全部边;连通路径只能经过本校学生。
请判断是否存在这样的划分。只需要回答是否存在,不需要输出划分方案。原图不一定连通,保证没有自环,允许重边。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例的第一行包含两个整数 。
接下来 行,每行包含两个整数 ,表示一条无向关系。
输出格式
对于每个测试用例,如果存在满足条件的划分,输出一行 Yes;否则输出一行 No。
数据范围
- ;
- ,且 ;
- ;
- ,;
- 同一输入文件中,所有测试用例的 之和不超过 , 之和也不超过 。
注意:不保证没有重边。
样例输入 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
样例说明
- 第一组可以把 和 分到两所学校。
- 第二组无论怎样划分,都无法满足全部条件。
- 第三组可以划分为 和 。
- 第四组可以划分为 和 。该样例包含重边,重边是合法的。