题解

思路

设 1 号顶点的卡片值为 $x$。

做法

图连通，因此沿边 BFS 后，每个顶点的值都能写成 $x\oplus d_v$，其中 $d_1=0$，边 $(u,v)$ 上的记录保证 $d_v=d_u\oplus X$。多余的非树边不会增加新的自由度。

若 $N$ 为偶数，所有顶点卡片的异或和中 $x$ 出现偶数次而抵消，故它等于 $\bigoplus_v d_v$。又因为顶点上恰好放置了 $0$ 到 $N$ 中除被吃掉数字外的所有卡片，所以答案为 $(\bigoplus_{i=0}^{N}i)\oplus(\bigoplus_v d_v)$。若 $N$ 为奇数，把一个合法赋值的所有卡片值同时翻转最低位，边上的异或均不变，并会得到另一个缺失数字，因此答案不唯一。

复杂度

每组数据只需一次 BFS，时间复杂度 $O(N+M)$，空间复杂度 $O(N+M)$。