记录编号	188492	评测结果	AAAAAAAAAA
题目名称	[POI 2003]可爱的猴子	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.758 s
提交时间	2015-09-23 17:07:01	内存使用	10.40 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define M 200005
using namespace std;

int n, m, r[M][3], des[M<<1][3], f[M], fail[M];
bool unexi[M][3];

vector <int> bel[M];

int find(int x){
	return f[x] = f[x]==x ? x : find(f[x]);
}

int main()
{
	freopen("monkeya.in","r",stdin);
	freopen("monkeya.out","w",stdout);
	memset(fail, -1, sizeof fail);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		f[i] = i;
		scanf("%d %d", r[i]+1, r[i]+2);
	}
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		des[i][v] = u;
		unexi[u][v] = 1;
	}
	for(int i = 1; i <= n; i++){
		int fi = find(i);
		for(int k = 1; k < 3; k++){
			if(r[i][k] > 0 && !unexi[i][k]){
			int fv = find(r[i][k]);
			if(fi != fv) f[fv] = fi;
			}
		}
	}
	int f1 = find(1);
	for(int i = 1; i <= n; i++){
		int fi = find(i);
		bel[fi].push_back(i); 
		if(fi != f1) fail[i] = m-1;
	}
	
	for(int i = m; i; i--){
		int u, v, fu, fv;
		if(des[i][1]){
			u = des[i][1];
			v = r[u][1];
		} 
		else{
			u = des[i][2];
			v = r[u][2];
		}
		fu = find(u);
		fv = find(v);
		f1 = find(1);
		if(fu == fv) continue;
		int su = bel[fu].size();
		int sv = bel[fv].size();
		if(fu == f1){
			for(int j = 0; j < sv; j++){
				fail[bel[fv][j]] = i-1;
			}
		}
		if(fv == f1){
			for(int j = 0; j < su; j++){
				fail[bel[fu][j]] = i-1;
			}
		}
		if(su < sv){
			f[fu] = fv;
			for(int j = 0; j < su; j++){
				bel[fv].push_back(bel[fu][j]);
			}
			bel[fu].clear();
		}
		else{
			f[fv] = fu;
			for(int j = 0; j < sv; j++){
				bel[fu].push_back(bel[fv][j]);
			}
			bel[fv].clear();
		}
	}
	for(int i = 1; i <= n; i++){
		printf("%d\n", fail[i]);
	}
	return 0;
}