logo AlgoBeat OnlineJudge
登录 注册

#214538. 【模板】弦图

内存限制:512 MiB 时间限制:300 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

模板题,无背景。

时间限制开 300ms 是为了卡部分时间复杂度退化成 或者其他时间复杂度的做法,正常做法不会被卡常。


你需要解决下面的问题:

定义一张图是弦图,当且仅当对于该图任意一个长度大于 的环,都存在一个弦。

现在给定一张 个点 条边的无向图,你需要判断该图是否是一张弦图。

若该图是一张弦图,则你还需要求:

  • 弦图的任意一个完美消除序列。
  • 弦图的最大团大小
  • 弦图的色数
  • 弦图的最大独立集大小

输入格式

本题有多组数据。

第一行一个整数 表示本题共有 组数据。

对于每组数据:

  • 第一行两个整数 表示这张图有 个顶点和 条边。
  • 然后 行,一行两个整数 表示该图的一条无向边。

保证图不存在重边,自环,但不保证图连通。

输出格式

若该图不是一张弦图,则只输出一行一个字符串 No

否则输出第一行一个字符串 Yes

然后一行一个长度为 的序列表示该弦图的任意一个完美消除序列。

然后一行 个整数,分别表示:

  • 弦图的最大团大小
  • 弦图的色数
  • 弦图的最大独立集大小

样例

样例输入 1

4
3 3
1 2
2 3
3 1
6 9
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 6
5 6
9 14
1 2
1 3
1 4
2 3
2 4
3 4
2 5
3 5
4 5
5 6
3 6
6 7
7 8
7 9
5 5
1 2
1 4
2 3
3 4
3 5

样例输出 1

Yes
1 2 3
3 3 1
Yes
1 2 3 4 5 6
3 3 2
Yes
1 2 4 3 5 6 8 7 9
4 4 4
No

数据范围与提示

对于全部的分数满足

特殊的,对于前 个测试点,满足 。该部分占 分。

图不存在重边,自环,但是不保证图连通。