记录编号	586615	评测结果	AAAAAAAAAA
题目名称	[POI 2003]可爱的猴子	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.341 s
提交时间	2024-02-18 22:04:02	内存使用	16.44 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 4e5+10,M = 4e5+10;
int n,m;
struct made{
	int s[3];
	bool f[3];
}a[N];
struct node{
	int x,op;
}q[N];
int ans[N];
struct uni{
	int fa[N];
	void init(){
		for(int i = 1;i <= n;i++)fa[i] = i;
	}
	int find(int x){
		if(x == fa[x])return x;
		return fa[x] = find(fa[x]);
	}
	void merge(int x,int y){
		if(x > y)swap(x,y);
		x = find(x),y = find(y);
		if(x > y)swap(x,y);
		if(x == y)return;
		fa[y] = x;
	}//y -> x
}U,f;	
int main(){
	freopen("monkeya.in","r",stdin);
	freopen("monkeya.out","w",stdout);
	scanf("%d%d",&n,&m);
	U.init();
	for(int i = 1;i <= n;i++)scanf("%d%d",&a[i].s[1],&a[i].s[2]);
	for(int i = 1;i <= m;i++){
		scanf("%d%d",&q[i].x,&q[i].op),a[q[i].x].f[q[i].op] = 1;
	}
	for(int i = 1;i <= n;i++){
		if(!a[i].f[1] && a[i].s[1] != -1)U.merge(i,a[i].s[1]);
		if(!a[i].f[2] && a[i].s[2] != -1)U.merge(i,a[i].s[2]);
	}
	f = U;
	ans[1] = -1;
	for(int i = m;i >= 1;i--){
		int x = q[i].x,y = a[q[i].x].s[q[i].op];
		if(y == -1)continue;
		int fx = f.find(x),fy = f.find(y);
		if(fx == fy)continue;
		if(fx > fy)swap(fx,fy),swap(x,y);
		if(fx == 1)ans[fy] = i-1;
		else U.fa[fy] = fx;
		f.fa[fy] = fx;
	}
	for(int i = 1;i <= n;i++)printf("%d\n",ans[U.find(i)]);

	return 0;
	
}