#18. Asm.Def的游戏

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

“这里是美国总统……透明计算网络产生了智能……10分钟前对我们发动攻击……我已命令核弹离线……告诉……”

接下来是“噗、噗”两声枪响。然后电话断了。

偌大的会议室里鸦雀无声。主席掐灭手中的烟头,“有把握吗,方教授?”

“我们不了解它,主席同志。透明计算网络是集群智能……”

“它是个游戏。”站在角落的Asm.Def大声插话道,所有人的目光投向他,“我擅长游戏。”

透明计算网络可以被视为包含n个节点,m条边的无向图。Asm.Def认为度数小于3的节点是非关键节点,因此他不断地从图中删去这样的节点,直到无点可删。然后Asm.Def想要求出剩下节点编号的异或值,这将是破解透明计算网络的关键。

输入格式

第一行两个整数,分别为n和m。即节点数量和边的数量。

接下来m行每行两个数,分别为u和v,表示有一条u到v的边。

保证没有自环,可能有重边。

输出格式

一行一个整数,为剩余节点编号的异或值。如果一个节点不剩,答案为0。

样例

样例输入

6 10
1 2
1 3
1 4
2 3
2 4
3 4
5 2
5 3
5 6
6 2

样例输出

4

样例解释

5和6号节点会删除,剩下节点异或值为1 xor 2 xor 3 xor 4 = 4

数据范围与提示

10%的数据:n <= 3

70%的数据:n <= 800,m <= 8000

100%的数据:n <= 100000,m <= 500000