P8056 C Numbers on a Graph

You are given an undirected graph with $n$ vertices and $m$ edges (**guaranteed to have no multiple edges and no self-loops, but not guaranteed to be connected**). Each edge has a distinct ID from $1$ to $m$. An edge is defined as an isolated edge if and only if both of its endpoints have already been deleted. You need to provide an order of deleting vertices. Let $P_i$ be the ID of the $i$-th edge that becomes an isolated edge. You need to minimize the lexicographic order of $P_i$. If at some moment multiple edges become isolated edges, we consider that the edge with the smaller ID becomes isolated first.

The first line contains two positive integers $n, m$, representing the number of vertices and edges in the graph. Lines $2$ to $m+1$: the $i$-th line contains two positive integers $x, y$, representing the two endpoints of the edge with ID $i-1$.

To reduce the output size, output $\bigoplus\limits_{i=1}^{m} i\times P_i$, where $\bigoplus$ denotes bitwise XOR in binary.

**[Sample Explanation #1]** The array $P$ is $\{1,3,4,6,8,2,5,7\}$. **[Constraints]** **This problem uses bundled testdata.** All testdata satisfies $1\le n\le 10^6$, $1\le m\le \min (10^6,\frac{n(n-1)}{2})$. The detailed constraints are as follows: - 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$, the graph is connected, and the degree of every vertex is at most $2$. - Subtask #5 (16 pts): $m=\dfrac{n(n-1)}{2}$. - Subtask #6 (15 pts): $n, m\le 10^5$. - Subtask #7 (11 pts): No additional constraints. Translated by ChatGPT 5