简要题意：

你有一张无向图，每个节点有颜色，每一轮变换中你需要为每一个点决定它在下一轮的颜色，可选颜色集合为它的颜色和它的所有邻居在这一轮中的颜色。

你需要用不超过20000轮操作来将100个节点的图的颜色从初始状态变为目标状态。

题解：

发现变换操作实际上非常强大，猜想对于一个连通块，只要初始颜色集合把目标态颜色集合包含了就不会有问题。

然后先找路径暴力调整颜色数，然后找路径暴力调整颜色位置。

由于路径长度最多是$O(n)$的，这个做法的调整次数最坏不超过$2n^2$。

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const using std::cerr; using std::cout; cs int N=1e2+7,M=2e4+7; int n,m,k; int st[N],col[N],ed[N]; std::vector<int> G[N]; struct node{int t,u,v;}; //t=0 swap(col[u],col[v]) else col[u]=col[v] std::vector<node> vec; std::vector<int> nd; int c1[N],c2[N]; int vis[N],h[N],id[N]; void dfs1(int u){ nd.push_back(u);vis[u]=true;++c1[st[u]],++c2[ed[u]]; for(int re v:G[u])if(!vis[v])dfs1(v); } bool dfs2(int u,int aim,int fa){ if(u==aim)return true;h[u]=true; for(int re v:G[u])if(!h[v]&&dfs2(v,aim,u)){ if(fa==-1)vec.push_back({1,u,v}),col[u]=col[v]; else vec.push_back({0,u,v}),std::swap(col[u],col[v]); return true; }return false; } bool dfs3(int u,int aim,int lim){ if(u==aim)return true;h[u]=true; for(int v:G[u])if(!h[v]&&id[v]<=lim&&dfs3(v,aim,lim)){ std::swap(col[u],col[v]),vec.push_back({0,u,v}); return true; }return false; } void solve(){ while(true){ bool ok=false; for(int u:nd) if(c1[col[u]]>c2[col[u]]){ ok=true; for(int v:nd) if(c1[col[v]]<c2[col[v]]){ c1[col[u]]--,c1[col[v]]++; memset(h,0,n<<2); dfs2(u,v,-1);break; } break; } if(!ok)break; } for(int re i=0;i<nd.size();++i)id[nd[i]]=i; for(int re i=nd.size()-1;~i;--i) if(col[nd[i]]!=ed[nd[i]]){ for(int re j=0;j<i;++j) if(col[nd[j]]==ed[nd[i]]){ memset(h,0,n<<2); dfs3(nd[i],nd[j],i); break; } } } signed main(){ #ifdef zxyoi freopen("hard.in","r",stdin); #endif scanf("%d%d%d",&n,&m,&k); for(int re i=0;i<n;++i)scanf("%d",st+i); for(int re i=0;i<n;++i)scanf("%d",ed+i); for(int re i=1;i<=m;++i){ int u,v;scanf("%d%d",&u,&v);--u,--v; G[u].push_back(v); G[v].push_back(u); }memcpy(col,st,n<<2); for(int re i=0;i<n;++i)if(!vis[i]){ memset(c1,0,k<<2); memset(c2,0,k<<2); nd.clear();dfs1(i); for(int re j=0;j<k;++j)if(c2[j]&&!c1[j]) puts("Impossible"),exit(0);solve(); } for(int re i=0;i<n;++i)cout<<st[i]<<" ";cout<<"\n"; for(auto &t:vec){ if(t.t)st[t.u]=st[t.v]; else std::swap(st[t.u],st[t.v]); for(int re i=0;i<n;++i)cout<<st[i]<<" ";cout<<"\n"; } return 0; }