#bzoj3108. [CQOI2013] 图的逆变换

[CQOI2013] 图的逆变换

题目描述

给一个nn结点mm条边的有向图DD,可以这样构造图E:给DD的每条边uvuv,在EE中建立一个点(u,v)(u,v),然后对于DD中的两条边u→vu\rightarrow v和v→wv\rightarrow w,在EE中从(u,v)(u,v)向(v,w)(v,w)连一条有向边。EE中不含有其他点和边。

输入EE,你的任务是判断是否存在相应的DD。注意,DD可以有重边和自环。

输入格式

第一行包含测试数据个数TT。

每组数据前两行为DD的边数(即E的点数)mm和EE的边数kk。

以下kk行每行两个整数x,yx,y,表示EE中有一条有向边x−>yx->y。EE中的点编号为0∼m−10\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

数据规模与约定

对于100%100\%的数据:T≤10,0≤m≤300T\le 10,0\le m\le 300.