若两个具有 $n$ 个顶点的无向图 $G_1$ 和 $G_2$ 存在一个排列 $p_1, p_2, \dots, p_n$，使得 $$(u, v) \text{ 是 } G_1 \text{ 的一条边} \iff (p_u, p_v) \text{ 是 } G_2 \text{ 的一条边}$$ 则称它们是同构的。

给定一个无向图 $G$，你需要判断与 $G$ 同构的本质不同的图的数量是否不超过 $n$ 个。

如果两个具有相同顶点数的无向图的边集不同，则认为它们是不同的。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示图的顶点数和边数。

接下来 $m$ 行，每行包含一对整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示 $u$ 和 $v$ 之间有一条边。

图中不包含自环或重边。保证所有测试用例中 $n$ 和 $m$ 的总和均不超过 $10^5$。

输出格式

对于每个测试用例，如果与给定图同构的本质不同的图的数量不超过 $n$ 个，则输出 YES，否则输出 NO。

样例

输入 1

3
3 3
1 2
2 3
3 1
3 2
1 2
2 3
5 5
1 2
2 3
3 4
4 5
5 1

输出 1

YES
YES
NO