The Restless Cat

Cheolmin keeps a cat. He built a multi-level playground for it, and the playground has $N$ rooms and $M$ corridors. The rooms are numbered 1 through $N$. Each corridor joins two different rooms and can be walked in both directions. At most one corridor joins any given pair of rooms. Every room is reachable from every other room along corridors. The playground is built in three dimensions, so no two corridors cross. The picture below shows a playground with 4 rooms and 5 corridors.

The cat is very restless and runs around the playground without stopping. It likes to pick $k$ distinct rooms $(k \ge 3)$, fix an order $(a_1, a_2, \ldots, a_k)$, and then run through that order again and again, so it visits $a_1, a_2, \ldots, a_k, a_1, a_2, \ldots, a_k, a_1, \ldots$ in turn. For such a run, $a_1$ and $a_2$, $a_2$ and $a_3$, ..., $a_k$ and $a_1$ must each be joined by a corridor.

Cheolmin worries that the cat tires itself out, so he wants to leave no repeating run at all. To keep the work small, he removes exactly one room and closes the corridors attached to it.

In the playground above the cat can run rooms 1, 2, 3 in that order, and it can also run rooms 1, 2, 4, 3 in that order. Removing room 2 leaves no repeating run. Removing room 3 gives the same result. Removing room 4 still leaves a repeating run.

You are given the rooms and the corridors. Find the number of a room whose removal destroys every repeating run. If several rooms work, find the sum of their numbers. If no room works, the answer is 0.

The first line contains the number of rooms $N$ and the number of corridors $M$, separated by a space. $(2 \le N \le 300\,000$, $1 \le M \le 300\,000)$

Each of the next $M$ lines contains the numbers of the two different rooms joined by one corridor. No pair of rooms appears more than once. The given playground has at least one repeating run.

If removing a single room destroys every repeating run, print the number of that room. If several rooms work, print the sum of their numbers. If no room works, print 0.

In the first example, removing room 2 works and removing room 3 works, so the answer is the sum 5.