Migrated from Lutece 3198 精神助产术

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

为了提高你的图论水平，拉帝奥教授决定考考你。

他给了你 $T$ 张无向连通图，其中第 $i$ 张图由 $n_i$ 个点和 $m_i$ 条边组成。

对于每一张图，你需要告诉他这张图的所有生成树是否都同构。对于两个树 $T_1$ 和 $T_2$ ，如果能够把树 $T_1$ 的所有点重新标号，使得树 $T_1$ 和树 $T_2$ 完全相同，那么这两个树是同构的。

Input

第一行一个整数 $T$ ，表示无向连通图的数量。

接下来对于每一张图：

第一行两个整数 $n_i$ 和 $m_i$ ，表示这张图的点数和边数。

接下来 $m$ 行，每行两个整数 $u_j$ 和 $v_j$ ，表示第 $j$ 条边连接的两个点。

Output

一共 $T$ 行，如果第 $i$ 张图的所有生成树都同构则在第 $i$ 行输出 YES ，否则输出 NO 。

Samples

4
4 3
1 2
2 3
2 4
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 1
3 4
1 0

YES
YES
NO
YES

Constraints

$1 \leq T \leq 10^5$

$1 \leq n_i \leq 10^5, n_i-1 \leq m_i \leq 10^5$

$1 \leq \sum _{i=1} ^{T} n_i ,\sum _{i=1} ^{T} m_i \leq 10^6$

$1 \leq u_j, v_j \leq n$

数据保证无重边与自环。

Resources

2024 UESTC ICPC Training for Graph