记录编号	210107	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的游戏	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2015-11-25 13:41:21	内存使用	1.55 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN (100005)
int N,M;
vector<int> adj[MAXN];
bool okey[MAXN];
//论stl的使用 
void read_data()
{
	int i;
	int u,v;
	scanf("%d %d", &N, &M);
	for(i = 0; i < M; i++)
	{
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}	
	memset(okey, true, sizeof(okey));
}

void solve()
{
	int i;
	int u,v;
	unsigned r = 0;
	queue<int> q;
	vector<int>::iterator it1;
	vector<int>::iterator it2;
	for(i = 1; i <= N; i++)
	{
		if(adj[i].size() < 3)
			q.push(i);
	}
	while(q.size())
	{
		u = q.front();
		q.pop();
		okey[u] = false;
		
		for(it1 = adj[u].begin(); it1 != adj[u].end(); ++it1)
		{
			v = *it1;
			for(it2 = adj[v].begin(); it2 != adj[v].end(); ++it2)
			{
				if(*it2 == u)
				{
					adj[v].erase(it2);
					break;
				}
			} 
			if(adj[v].size() < 3)
			{
				q.push(v);
			}
		}
	}
	for(i = 1; i <= N; i++)
	{
		if(okey[i])
			r = r^i;
	}
	printf("%u\n", r);
}

int main()
{
	freopen("asm_game.in", "r", stdin);
	freopen("asm_game.out", "w", stdout);
	read_data();
	solve();
	return 0;
}