题目背景

模板题，无背景。

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

题目描述

你需要解决下面的问题：

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

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

若该图是一张弦图，则你还需要求：

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

输入格式

本题有多组数据。

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

对于每组数据：

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

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

输出格式

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

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

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

然后一行 $3$ 个整数，分别表示：

• 弦图的最大团大小 $\omega$。
• 弦图的色数 $\chi$。
• 弦图的最大独立集大小 $\alpha$。

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

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

提示

对于全部的分数满足 $1\le T\le 100,3\le n\le 10^5,0\le m\le 3\times 10^5,\sum n\le 2\times 10^5,\sum m\le 6\times 10^5$。

特殊的，对于前 $8$ 个测试点，满足 $n,m\le 100,\sum n,\sum m\le 500$。该部分占 $40$ 分。

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