1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define for_edge(i, x) for(RG int i=head[x];i;i=e[i].next)
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
#define yes "Yes"
#define no "No"
const int maxn(2e4+10), maxm(1e5+10);
struct edge { int next, to; } e[maxm];
int head[maxn], e_num, T, n, m, a, b, dfn[maxn], low[maxn], stk[maxn], top, cnt;
bool tag, vis[maxn];
inline void add_edge(int from, int to) { e[++e_num]=(edge){head[from], to}; head[from]=e_num; }
inline void pop(int u)
{
int x=0;
while(stk[top]!=u) vis[stk[top]]=false, top--, x++;
vis[stk[top]]=false; top--; x++;
if(x>1) tag=true;
}
inline void Tarjian(int x)
{
low[x]=dfn[x]=++cnt; stk[++top]=x; vis[x]=true;
for_edge(i, x)
{
int to=e[i].to;
if(!dfn[to])
{
Tarjian(to);
low[x]=min(low[x], low[to]);
}
else if(vis[to]) low[x]=min(low[x], dfn[to]);
}
if(dfn[x]==low[x]) pop(x);
}
int main()
{
T=read();
while(T--)
{
clear(head, 0); e_num=0; clear(dfn, 0); clear(low, 0);
n=read(); m=read(); tag=false; cnt=0;
for(RG int i=1;i<=m;i++) { a=read(); b=read(); add_edge(a, b); }
for(RG int i=1;i<=n;i++) if(!dfn[i]) Tarjian(i);
if(tag) puts(no);
else puts(yes);
}
return 0;
}
|