有一幅无向连通图G(n,m)，无重边无自环。
You are given two k-colourings s and t. You want to transform from s to t step by step. In each step, each vertex may change its colour to one of its neighbours’ colour, or keep its current colour.
求出任意方案，步数不超过20000，n<=100
建出原图任意一个生成树。
只要t中每个用到的颜色都在s中出现，就一定有解，否则一定无解。
显然我们可以用不超过2n步 交换 2点的颜色，或让一个点 改变 为另一个点的颜色。
于是我们用前若干步对每种颜色通过交换到达t中的点，此后用这些点改变剩余点。
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cerr<<a[i][j]<<' ';\
cerr<<a[i][m]<<endl; \
}
#pragma
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n,m,k;
#define
vi e[MAXN];
bool b[MAXN];
int dep[MAXN]={},fa[MAXN]={},col[MAXN]={},aim[MAXN]={};
int cnt=0;
int a[40010][1010];
vi aim2,col2;
int id[MAXN],tot=0;
bool f[MAXN][MAXN];
void dfs(int x,int f){
aim2.pb(aim[x]);
col2.pb(col[x]);
id[++tot]=x;
b[x]=1; fa[x]=f,dep[x]=dep[f]+1;
for(auto v:e[x]) if (!b[v]) {
dfs(v,x);
}
}
int son[MAXN];
int lca(int x,int y) {
while (dep[x]<dep[y]) y=fa[y];
while (dep[x]>dep[y]) son[fa[x]]=x,x=fa[x];
while(x^y) son[fa[x]]=x,x=fa[x],y=fa[y];
return x;
}
int switch_color_of(int x,int y,vi &v) {
int g=lca(x,y);
while(y!=g) {
v.pb(y);
y=fa[y];
}
while(x!=g) {
v.pb(g);
g=son[g];
}
v.pb(x);
}
int sta[MAXN];
void solve(vi v) {
Rep(i,SI(v)-1) {
swap(col[v[i]],col[v[i+1]]);
if (!f[v[i]][v[i+1]]) while(1);
++cnt;
For(j,n) a[cnt][j]=col[j];
}
}
void solve2(vi v) {
ForD(i,SI(v)-2) {
swap(col[v[i]],col[v[i+1]]);
++cnt;
For(j,n) a[cnt][j]=col[j];
}
col[v[1]]=col[v[0]];
++cnt;
For(j,n) a[cnt][j]=col[j];
For(i,SI(v)-2){
swap(col[v[i]],col[v[i+1]]);
++cnt;
For(j,n) a[cnt][j]=col[j];
}
}
void solve3(vi v) {
ForD(i,SI(v)-2) {
swap(col[v[i]],col[v[i+1]]);
++cnt;
For(j,n) a[cnt][j]=col[j];
}
swap(col[v[1]],col[v[0]]);
++cnt;
For(j,n) a[cnt][j]=col[j];
For(i,SI(v)-2){
swap(col[v[i]],col[v[i+1]]);
++cnt;
For(j,n) a[cnt][j]=col[j];
}
}
void calc() {
Rep(i,SI(aim2)) {
int c=aim2[i],p,t;
For(i,tot) {
if (col[id[i]] == c) p=id[i];
if (aim[id[i]] == c) t=id[i];
}
if (aim[p]==c) {
sta[c]=p; continue;
}
vi v;
switch_color_of(t,p,v);
solve3(v);
sta[c]=t;
}
For(i,tot) {
int x = id[i];
if (col[x]==aim[x]) continue;
vi v;
if (x==sta[aim[x]]) continue;
switch_color_of(x,sta[aim[x]],v);
solve2(v);
}
}
int main()
{
// freopen("make_data.in","r",stdin);
// freopen("a.out","w",stdout);
while(scanf("%d%d%d",&n,&m,&k)==3) {
MEM(f)
For(i,n) col[i]=read();
For(i,n) aim[i]=read();
For(i,m) {
int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
f[u][v]=f[v][u]=1;
}
dep[0]=1;
For(i,n) b[i]=0;
bool fl=1;
cnt=1;
For(i,n) {
a[cnt][i]=col[i];
}
For(i,n) if (!b[i]) {
tot=0;
aim2.clear();
col2.clear();
dfs(1,0);
sort(ALL(aim2));
aim2.erase(unique(ALL(aim2)),aim2.end());
sort(ALL(col2));col2.pb(1E9);
col2.erase(unique(ALL(col2)),col2.end());
Rep(i,SI(aim2)) {
int p=lower_bound(ALL(col2),aim2[i])-col2.begin();
if (col2[p]!=aim2[i]) {
fl=0;break;
}
}
if( !fl) break;
calc();
}
if(cnt>20000) while(1);
if(fl) {
For(i,cnt) {
For(j,n-1) cout<<a[i][j]<<' ';cout<<a[i][n]<<endl;
}
}else puts("Impossible");
For(i,n) e[i].clear();
}
return 0;
}