Problem Description

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.

Input Format

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$.

Output Format

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

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

44

Hint

[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