记录编号	293942	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]seq	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	4.236 s
提交时间	2016-08-11 15:46:15	内存使用	33.80 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("hzoi_seq.in","r",stdin);freopen("hzoi_seq.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=1000010;
struct op{
	int pos,n;
}r[maxn*3];
int poi[maxn];
int fath[maxn*3];
int ans[maxn],cnt=0;
short c[15];
void schange(int x,int y){
	fath[poi[x]]=poi[y];
	cnt++;r[cnt].n=x;poi[x]=cnt;
}
void findfath(int x){
	if(fath[x]==x){
		return;
	}findfath(fath[x]);
	fath[x]=fath[fath[x]];
}
int read(){
	char c;int ans=0;
	while(c=getchar(),c<'0'||c>'9')if(c==EOF)return -1;
	ans=(ans*10)+c-48;
	while(c=getchar(),c<='9'&&c>='0')ans=(ans*10)+c-48;
	return ans;
}
void print(int x){
	int cnt=0;
	if(x==0){putchar(48);putchar(' ');return;}
	while(x>0){
		c[++cnt]=x%10;
		x=x/10;
	}for(int i=cnt;i>0;i--)putchar(c[i]+48);putchar(' ');
}
void chul(){
	int n,m,q,a,b;n=read();m=read();q=read();
	for(int i=1;i<=m+n+q;i++)fath[i]=i;
	for(int i=1;i<=m;i++){
		poi[i]=i;
		r[i].n=i;
	}int x;cnt=m;
	for(int i=1;i<=n;i++){
		x=read();
		fath[++cnt]=x;
		r[cnt].pos=i;
		r[cnt].n=x;
	}
	for(int i=1;i<=q;i++){
		a=read();b=read();
		if(a==b)continue;
		schange(a,b);
	}for(int i=1;i<=cnt;i++){
		findfath(i);
		ans[r[i].pos]=r[fath[i]].n;
	}for(int i=1;i<=n;i++){
		print(ans[i]);
	}
}
int main(){
	Begin;
}
/*
5 5 3
1 2 3 4 5
3 1
4 3
1 5

5 4 3
1 2 3 4 3
3 1
1 4
4 2
*/