CF1783F

好像是一种不一样的建模方法。

首先我们会做只有 $a$ 的情况：每个 $i\to a_i$ 连边，答案即为 $n-cntc$，其中 $cntc$ 为环的个数。

考虑加上 $b$ 后怎么做。考虑补集转化，每个环内可以选一个数，不去操作它，只操作其他的，它也可以自动归位。此时问题就变成：给你一个长度为 $n$ 的 $01$ 序列和 $m$ 个性质，形如集合 $S$ 中每个位置，其中最多只能有一个 $1$。

正常做是困难的，但是发现这些的集合相当于分成了两组（$a$ 产生的集合和 $b$ 产生的），每组中的集合交集为空，并集为全部位置。则可以如下网络流建模：

设 $a$ 产生的集合为 $S_i$，$b$ 产生的为 $T_j$，源点为 $s$，汇点为 $t$。

• $\forall i$，连 $s\to S_i$。
• $\forall x\in S_i$，连 $S_i\to x$。
• $\forall j$，连 $T_j\to t$。
• $\forall y\in T_j$，连 $y\to T_j$。

（上面的表达可能不够严谨，看懂就行）

流量均为 $1$。答案即为 $n-maxflow$。这是一个单位容量的图，所以 dinic 的复杂度大致是 $O(n\sqrt n)$ 的，可以通过。

输出方案直接在残量网络上找起点为 $i$ 的边（容易发现只有一条）检查流量是否为 $0$ 即可。

code：

int n,m,dis[N],cur[N],a[N],b[N];
bool vis[N];
static int S,T;
int tot=1,head[N];
struct node{int to,nxt,fl;}e[N<<2];
vector<int> g;
il void add(int u,int v,int f){
	e[++tot]={v,head[u],f},head[u]=tot;
	e[++tot]={u,head[v],0},head[v]=tot;
}
bool bfs(){
	mems(dis,0),memcpy(cur,head,sizeof head);
	queue<int> q;
	dis[S]=1,q.push(S);
	while(q.size()){
		int u=q.front();q.pop();
		go(i,u){
			int v=e[i].to;
			if(dis[v]||!e[i].fl)continue;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
	return dis[T];
}
int dfs(int u,int f){
	if(u==T)return f;
	int s=0;
	for(int &i=cur[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dis[v]!=dis[u]+1||!e[i].fl)continue;
		int l=dfs(v,min(e[i].fl,f-s));
		s+=l;
		e[i].fl-=l,e[i^1].fl+=l;
		if(s==f)break;
	}
	return s;
}
int dinic(){
	int ret=0;
	while(bfs())ret+=dfs(S,inf);
	return ret;
}
void Yorushika(){
	scanf("%d",&n),m=n;
	rep(i,1,n)scanf("%d",&a[i]);
	rep(i,1,n)scanf("%d",&b[i]);
	S=3*n+1,T=S+1;
	rep(i,1,n){
		if(vis[i])continue;
		int u=a[i];g.clear();
		while(u!=i)g.eb(u),vis[u]=1,u=a[u];
		g.eb(u),vis[u]=1,m++;
		add(S,m,1);
		for(int j:g)add(m,j,1);
	}
	mems(vis,false);
	rep(i,1,n){
		if(vis[i])continue;
		int u=b[i];g.clear();
		while(u!=i)g.eb(u),vis[u]=1,u=b[u];
		g.eb(u),vis[u]=1,m++;
		add(m,T,1);
		for(int j:g)add(j,m,1);
	}
	printf("%d\n",n-dinic());
	for(int i=2;i<=tot;i+=2){
		int u=e[i].to;
		if(u<=n&&e[i].fl)printf("%d ",u);
	}
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}