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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
inline int read(){
int w=0,x=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=2e5+10,maxm=5e5+10;
typedef pair<int,int> pii;
int n,m;
struct gragh{
int ecnt,head[maxn],to[maxm<<1],nxt[maxm<<1];
inline void addedge(int a,int b){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
}
}G1,G2;
int tot,cnt,st[maxn],dfn[maxn],low[maxn];
map<pii,int> mp;
void tarjan(int x,int f){
dfn[x]=low[x]=++tot;
st[++st[0]]=x;
for(int i=G1.head[x];i;i=G1.nxt[i]){
int u=G1.to[i];
if(u==f)continue;
if(!dfn[u]){
tarjan(u,x);
low[x]=min(low[x],low[u]);
if(low[u]>=dfn[x]){
cnt++;
if(low[u]>dfn[x]) mp.insert(make_pair(minmax(u,x),cnt));
G2.addedge(cnt,x);
int now=-1;
while(now^u)
now=st[st[0]--],G2.addedge(now,cnt);
}
}else low[x]=min(low[x],dfn[u]);
}
}
int fa[maxn],dep[maxn],top[maxn],son[maxn],siz[maxn];
void dfs1(int x,int f){
fa[x]=f,dep[x]=dep[f]+1;siz[x]=1;
for(int i=G2.head[x];i;i=G2.nxt[i]){
int u=G2.to[i];
if(u==f)continue;
dfs1(u,x);
siz[x]+=siz[u];
if(siz[u]>siz[son[x]])son[x]=u;
}
}
void dfs2(int x,int topf){
top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=G2.head[x];i;i=G2.nxt[i]){
int u=G2.to[i];
if(u==fa[x] or u==son[x]) continue;
dfs2(u,u);
}
}
inline bool LCA(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
if(top[x]==top[z] and dep[z]<=dep[x]) return 1;
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
if(top[x]==top[z] and dep[z]>=dep[y] and dep[z]<=dep[x]) return 1;
return 0;
}
inline void work(){
n=cnt=read(),m=read();
for(int i=1;i<=m;i++) G1.addedge(read(),read());
tarjan(1,0);
dfs1(1,0);
dfs2(1,1);
int Q=read();
while(Q--)
if(read()==1){
int x=read(),y=read();
map<pii,int>::iterator it=mp.find(minmax(read(),read()));
if(it==mp.end()) puts("yes");
else puts(LCA(x,y,(*it).second)?"no":"yes");
}else{
int x=read(),y=read(),z=read();
puts(LCA(x,y,z)?"no":"yes");
}
}
}
signed main(){
star::work();
return 0;
}
|
