# T1.relation(亲戚)

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 5001

using namespace std;

int fa[MX];
int n,m,p;

int findfa(int x){return fa[x]==x?x:(fa[x]=findfa(fa[x]));}

void comb(int a,int b){fa[findfa(a)]=findfa(b);}

int main()
{
freopen("relation.in","r",stdin);
freopen("relation.out","w",stdout);
int a,b;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
comb(a,b);
}
for(int i=1;i<=p;i++)
{
scanf("%d%d",&a,&b);
if(findfa(a)==findfa(b))printf("Yes\n");
else printf("No\n");
}
return 0;
}


# T2.gangs(黑社会团伙)

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 5001

using namespace std;

int fa[MX],dis[MX];
int kind[MX];
int n,m;

int findfa(int x)
{
if(fa[x]==x)return x;
else
{
findfa(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=fa[fa[x]];
return fa[x];
}
}

void frid(int a,int b)
{
int f1,f2;
f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
if(dis[a]%2==dis[b]%2)dis[f1]=0;
else dis[f1]=1;
}

void enem(int a,int b)
{
int f1,f2;
f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
if(dis[a]%2!=dis[b]%2)dis[f1]=0;
else dis[f1]=1;
}

int main()
{
freopen("gangs.in","r",stdin);
freopen("gangs.out","w",stdout);
char op;
int a,b;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
op=getchar();
while(op!='E'&&op!='F')op=getchar();
scanf("%d%d",&a,&b);
if(op=='E')enem(a,b);
else frid(a,b);
}
for(int i=1;i<=n;i++)
{
findfa(i);
if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
}
for(int i=1;i<=n;i++)
{
if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
}
int tot=0;
for(int i=1;i<=n;i++)tot+=kind[i];
printf("%d\n",tot);
return 0;
}


# T3.filling(矩形填补)

1. 一个点可以将它所在的横线和竖线连接起来。
2. 两个已经被连接起来的线的交点一定是一个黑点。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1000010

using namespace std;

typedef struct sfga
{
int x,y;
int sx,sy;
}point;

int fa[MX],mx,my;
int ynum[MX],xnum[MX];
char vis[MX];
point src[MX/2];
int n;

int cmpx(point a,point b){if(a.x==b.x)return a.y<b.y;else return a.x<b.x;}

int cmpy(point a,point b){if(a.y==b.y)return a.x<b.x;else return a.y<b.y;}

int findfa(int x){return x==fa[x]?x:(fa[x]=findfa(fa[x]));}

void comb(int a,int b)
{
if(findfa(a)==findfa(b))return;
xnum[findfa(b)]+=xnum[findfa(a)];
ynum[findfa(b)]+=ynum[findfa(a)];
fa[findfa(a)]=findfa(b);
}

int main()
{
freopen("filling.in","r",stdin);
freopen("filling.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&src[i].x,&src[i].y);
sort(src+1,src+n+1,cmpx);
for(int now=0,i=1;i<=n;i++)
{
if(src[i].x!=src[i-1].x||i==1)now++;
src[i].sx=now;
mx=now;
}
sort(src+1,src+n+1,cmpy);
for(int now=0,i=1;i<=n;i++)
{
if(src[i].y!=src[i-1].y||i==1)now++;
src[i].sy=now;
my=now;
}
for(int i=1;i<=mx+my;i++)fa[i]=i;
for(int i=1;i<=mx;i++)xnum[i]=1;
for(int i=mx+1;i<=mx+my;i++)ynum[i]=1;
for(int i=1;i<=n;i++)comb(src[i].sx,src[i].sy+mx);
long long ans=0;
for(int i=1;i<=mx+my;i++)
{
if(vis[findfa(i)])continue;
ans+=(long long)xnum[fa[i]]*(long long)ynum[fa[i]];
vis[fa[i]]=1;
}
cout<<ans<<endl;
return 0;
}


# T4.game(格子游戏)

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 2000010

using namespace std;

int fa[MX],n,m;

int findfa(int x){return (x==fa[x]?x:(fa[x]=findfa(fa[x])));}

int comb(int a,int b)
{
if(findfa(a)==findfa(b))return 1;
fa[findfa(a)]=findfa(b);
return 0;
}

int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int x,y;
char c;
scanf("%d%d",&n,&m);
for(int i=1;i<=n*(n+1);i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
c=getchar();
while(c!='D'&&c!='R')c=getchar();
if(c=='D')
{
if(comb((x-1)*(n+1)+y,x*(n+1)+y))
{
cout<<i<<endl;
return 0;
}
}
else
{
if(comb((x-1)*(n+1)+y,(x-1)*(n+1)+y+1))
{
cout<<i<<endl;
return 0;
}
}
}
cout<<-1<<endl;
return 0;
}


# T5.lyp(打怪兽)

1 a b c: 告诉你 a 怪兽比 b 怪兽强 c
2 a b：询问 a 和 b 谁强。如果一样强或不知道，就输出 0

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 31000

using namespace std;

int fa[MX],dis[MX];
int n,q;

int findfa(int x)
{
if(fa[x]==x)return x;
else
{
findfa(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=fa[fa[x]];
return fa[x];
}
}

void big(int a,int b,int c)
{
int f1=findfa(a),f2=findfa(b);
if(f1==f2)return;
fa[f1]=f2;
dis[f1]=dis[b]-dis[a]+c;
}

int query(int a,int b)
{
int f1=findfa(a),f2=findfa(b);
if(f1!=f2)return 0;
if(dis[a]==dis[b])return 0;
return (dis[a]>dis[b]?a:b);
}

int main()
{
freopen("lyp.in","r",stdin);
freopen("lyp.out","w",stdout);
int op,a,b,c;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=q;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&a,&b,&c);
big(a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%d\n",query(a,b));
}
}
return 0;
}