9527 - 图的逆变换

给一个 n 结点 m 条边的有向图 D,可以这样构造图 E:给 D 的每条边 (u,v),在 E 中建立一个点 uv,然后对于 D 中的两条边 (u,v)(v,w),在 E 中从 uvvw 连一条有向边。E 中不含有其他点和边。

输入 E,你的任务是判断是否存在相应的 D

注意,D 可以有重边和自环。

输入

第一行包含测试数据个数 TT\leq 10)。

对于每组数据:

第一行一个整数 m0\le m\le300),表示 D 的边数(即 E 的点数)。

第二行一个整数 k,表示 E 的边数。

以下 k 行每行两个整数 x, y,表示 E 中有一条有向边 (x,y)E 中的点编号为 0\sim m-1

输出

对于每组数据输出一行。如果存在,输出 Yes,否则输出 No

样例

输入

4
2
1
0 1
5
0
4
3
0 1
2 1
2 3
3
9
0 1
0 2
1 2
1 0
2 0
2 1
0 0
1 1
2 2

输出

Yes
Yes
No
Yes

来源

重庆省选

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题