[Contest #0]项链与计数

内存限制：256 MB 时间限制：4000 ms

在图论中，“简单环” 被定义为一个点数和边数相等的回路，并且这条回路上没有出现重复的点或边。

对于一个无向图，小象定义 “项链” 是由一些简单环组成的子图，不妨设项链包括 $k$ 个简单环 $C_1$, $C_2$, $\ldots$, $C_k$ ($k \in \mathbb{N}^+$)，那么项链需要满足：

当且仅当 $|i - j| \leq 1$ 时，简单环 $C_i$ 和 $C_j$ 共用顶点；
简单环 $C_i$ 和 $C_{i +1}$ 恰好共用一个顶点；
任意两个不同的简单环 $C_i$ 和 $C_j$ ($i \neq j$) 没有共用边。

注意，按照上述定义，一个简单环也可以看做是项链。

小象画了一个 $n$ 个点的无向图，其中点被从 $1$ 到 $n$ 编号。最开始图中没有任何一条边，然后他往图中依次添加了 $m$ 条无向边，整个图逐渐变得复杂起来。

他很好奇，在他每添加了一条边之后，整个图里存在多少对点 $(u, v)$ 满足 $u \neq v$，且存在一个项链 $C_1$, $C_2$, $\ldots$, $C_k$ 使得 $u \in C_1$, $v \in C_k$。需要一提的是，小象认为 $(u, v)$ 和 $(v, u)$ 是相同的点对。

不妨设在添加了 $i$ 条边后这样的点对数量为 $f(i)$，小象希望你能帮他计算 $\bigoplus\limits_{i = 1}^{m}{(i \cdot f(i))}$的值，这里 $\oplus$ 表示按位异或运算符。

输入包含多组测试数据。输入的第一行包含一个正整数 $T$ ($1 \leq T \leq 1000$)，表示测试数据的组数。接下来依次描述每组测试数据，对于每组测试数据：

第一行包含两个正整数 $n$ 和 $m$ ($2 \leq n \leq 10^6$, $1 \leq m \leq 2 \times 10^6$)，含义如题面所示。

接下来 $m$ 行，第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \leq u, v \leq n$, $u \neq v$)，表示第 $i$ 条无向边连接的两点编号为 $u$ 与 $v$。注意，即使给出的某两条边连接了相同的一对点，它们也被认为是不同的两条边。

保证所有测试数据的 $n$ 之和不超过 $10^6$，所有测试数据的 $m$ 之和不超过 $2 \times 10^6$。

对于每组数据，输出一行，包含一个整数，表示所求的值。

样例输入 1

样例输出 1

下图给出了样例对应的图，其中边按照出现时间编号。

对于样例数据，有 $f(1) = f(2) = f(3) = 0$, $f(4) = 3$, $f(5) = f(6) = 6$，而$12 \oplus 30 \oplus 36 = 54$。

C1198 [Contest #0]项链与计数

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示