[R23F]寻路 - 代码源竞赛平台

时空限制

2S/256M

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图，点从 $1$ 到 $n$ 编号。

你需要回答 $n + 1$ 个询问，对于每个 $i = 0, 1,\cdots, n$，你需要回答以下问题：

定义一条从 $1$ 到 $n$ 的路径是符合条件的，当且仅当路径中被访问了两次的点（即重访点）的数量不超过 $i$ 个，路径中所有其他的点最多只能被访问一次。

对于给定的 $i$，你需要计算出所有符合上述条件的路径所能经过的点的总数。换句话说，一个点 $v$ 是可被计入的，只要存在至少一条满足条件的 $1 \to n$ 路径经过了 $v$。

由于输出量过大，你不需要逐一输出每个 $i$ 的答案。请计算出这 $n + 1$ 个答案的异或和，并输出这个最终结果。

格式

输入格式

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

接下来 $m$ 行，每行包含两个整数 $u,v$，表示点 $u$ 和点 $v$ 之间存在一条无向边。

输出格式

输出一个整数，表示 $n + 1$ 个答案的异或和。

样例

样例输入 #1

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

样例输出 #1

6

样例解释 #1

答案数组如下：$[3,5,5,5,5,5]$。异或和为 $6$。

数据规模

对于 $25 \%$ 的数据，$1 \leq n \leq 10$，$1 \leq m \leq 12$。

对于 $100 \%$ 的数据，$1 \leq n \leq 1 \times 10^6$，$1 \leq m \leq 1 \times 10^6$，保证给定的图是连通的，且不含重边和自环。