题目描述

给定一个 $n$ 个点 $m$ 条边的无向图（保证无重边无自环但不保证连通），每条边有一个 $1\sim m$ 的互不相同的编号。

定义一条边是孤边，当且仅当它的两端点均已经被删除。

您需要给定一个删点顺序，令 $P_i$ 表示第 $i$ 条变成孤边的边的编号，您需要最小化 $P_i$ 的字典序。

若某一时刻存在多条边变为孤边，我们认为，编号小的边先变为孤边。

输入格式

第一行两个正整数 $n,m$，表示图的点数和边数。

第 $2\sim m+1$ 行，第 $i$ 行两个正整数 $x,y$，表示编号为 $i-1$ 的边的两个端点。

输出格式

为减少输出量，请输出 $\bigoplus\limits_{i=1}^{m}i\times P_i$，其中 $\bigoplus$ 表示二进制下的按位异或。

6 8
1 2
4 5
6 3
5 2
3 4
5 1
1 4
3 5

44

提示

【样例解释 #1】

数组 $P$ 为 $\{1,3,4,6,8,2,5,7\}$。

【数据范围】

本题采用捆绑测试。

所有数据满足 $1\le n\le 10^6$，$1\le m\le \min (10^6,\frac{n(n-1)}{2})$。详细数据范围如下：

• Subtask #1 (12 pts): $n,m\le 10$。
• Subtask #2 (17 pts): $n,m\le 100$。
• Subtask #3 (11 pts): $n,m\le 5\times 10^3$。
• Subtask #4 (18 pts): $m=n-1$，图连通，所有点度数不超过 $2$。
• Subtask #5 (16 pts): $m=\dfrac{n(n-1)}{2}$。
• Subtask #6 (15 pts): $n,m\le 10^5$。
• Subtask #7 (11 pts): 没有任何附加限制。