#P4594. [Shoi2015]零件组装机

    ID: 1769 传统题 1500ms 256MiB 尝试: 137 已通过: 54 难度: 8 上传者: 标签>难度分类提高+/省选-离线与分治分治算法枚举与搜索暴力枚举数论倍数枚举排序与序列处理二分查找CF2500

[Shoi2015]零件组装机

[SHOI2015] 零件组装机

题目描述

曾经发明了激光发生器的发明家 SHTSC 又公开了他的新发明:零件组装机——一种可以生产并组装零件的神秘装置。

一个零件是一张顶点由 00 到 n−1n-1 标号的无向图,零件组装机有以下两种功能:

  1. 生产一个只有顶点 00、没有边的零件。
  2. 取顶点数分别为 n,mn,m 的两个零件 G1,G2G_1,G_2,其中 n≤mn\le m。保留 G1G_1 的编号,把 G2G_2 中原编号 ii 改为 n+in+i。保留两件内部的所有边,并对每个新编号 a∈[n,n+m−1]a\in[n,n+m-1] 添加一条连接 aa 与 a mod na\bmod n 的无向边。

生产单个零件及合并两件零件的示意

现在 SHTSC 正在思考,对于一个给定的零件,能否由零件组装机生产组装得到。注意:零件是带标号的,这意味着两个零件即使仅有标号不同也被视为不同的零件。为了帮助你理解问题,SHTSC 特地给了你顶点数 ≤5\le 5的所有零件的图例。

顶点数不超过五时的零件图

输入格式

第一行一个整数 tt ,表示有 tt 组数据。

每组数据的第一行有两个整数 nn,mm,表示某个带标号的无向图有 nn 个从 00 到 n−1n - 1 标号的顶点,以及 mm 条边。 接下来 mm 行,每行两个整数 u,vu,v ,表示一条连接 uu 与 vv 的无向边,0≤u,v<n0\le u,v<n。输入可以含自环或重复的边。判断输入的图能否原样由组装机得到。

输出格式

对于每组数据,输出一行。如果这个无向图可以被零件制造机制造,输出 YES,否则输出 NO。

3
1 0
2 0
4 6
0 1
0 2
1 2
1 3
2 3
3 0
YES
NO
YES

数据范围

对于 5%5\% 的数据,给定的图连通且 m=n−1m = n - 1; 对于另 15%15\% 的数据,n≤5n \leq 5; 对于 50%50\% 的数据,n≤1000n \leq 1000; 对于所有测试点,1≤t≤101\le t\le10,1≤n≤1051\le n\le10^5,0≤m≤1050\le m\le10^5。