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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=3e4+5,maxv=205,maxm=2e6+5;
int cnt,Cir[maxv],rec[maxn],x1[maxn],y1[maxn],x2[maxn],y2[maxn];
int tot,dfn[maxn],low[maxn],_n;
int ecnt,head[maxm],nxt[maxm],to[maxm],belong[maxn];
bool cir[maxv][maxv];
inline void addedge(int from,int too)
{
to[++ecnt]=too,nxt[ecnt]=head[from],head[from]=ecnt;
}
int st[maxn],top;
bool vis[maxn];
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
st[++top]=x;vis[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int u=to[i];
if(!dfn[u]){
tarjan(u);
low[x]=min(low[x],low[u]);
}else if(vis[x]){
low[x]=min(low[x],dfn[u]);
}
}
if (dfn[x] == low[x]) {
int v; belong[x] = ++_n;vis[x]=0;
while (v = st[top--], v != x) belong[v] = _n,vis[v]=0;
}
}
inline bool check()
{
for(int i=1;i<=(cnt<<1);i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=cnt;i++)
if(belong[i]==belong[i+cnt])return false;
return true;
}
inline void work()
{
int T,n,m;
n=read(),m=read();
memset(head,0,sizeof head);
memset(x1,0,sizeof x1);
memset(y1,0,sizeof y1);
memset(x2,0,sizeof x2);
memset(y2,0,sizeof y2);
memset(belong,0,sizeof belong);
memset(rec,0,sizeof rec);
memset(cir,0,sizeof cir);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(to,0,sizeof to);
memset(nxt,0,sizeof nxt);
memset(vis,0,sizeof vis);
memset(st,0,sizeof st);
ecnt=tot=cnt=_n=top=0;
for(int i=1;i<=m;i++)
{
x1[i]=read(),y1[i]=read();
if(x1[i]>y1[i]) swap(x1[i],y1[i]);
}
rec[Cir[1]=read()]=1;
for(int i=2;i<=n;i++){
rec[Cir[i]=read()]=i;
(Cir[i]>Cir[i-1]?cir[Cir[i-1]][Cir[i]]:cir[Cir[i]][Cir[i-1]])=1;
}
(Cir[1]>Cir[n]?cir[Cir[n]][Cir[1]]:cir[Cir[1]][Cir[n]])=1;
if(m>3*n-6){
printf("NO\n");return;
}
for(int i=1;i<=m;i++)
{
if(cir[x1[i]][y1[i]])continue;
x2[++cnt]=x1[i],y2[cnt]=y1[i];
}
for(int i=1;i<cnt;i++)
for(int j=i+1;j<=cnt;j++)
{
int a=rec[x2[i]] , b=rec[y2[i]] , x=rec[x2[j]] , y=rec[y2[j]];
if(a>b)swap(a,b);if(x>y)swap(x,y);
if((a<x and b>x and y>b) or (x<a and y>a and b>y))
addedge(i,j+cnt),addedge(j,i+cnt),addedge(i+cnt,j),addedge(j+cnt,i);
}
if(check())printf("YES\n");
else printf("NO\n");
}
}
int main()
{
int T=read();
while(T--) star::work();
return 0;
}
|
