Futurama

The setting is season 6, episode 10 of Futurama, The Prisoner of Benda.

Professor Farnsworth's mind switching device takes two bodies and exchanges the minds inside them. It has one design flaw. Once it has switched the minds of a pair of bodies, it refuses to work on that same pair again.

A business grew out of that flaw. When a group of customers can no longer stand the confusion and asks for their own minds back, Tate and Dixon arrive with their own bodies and a brand new device. The new device carries no usage history, so during the restoration a pair of bodies the old device already worked on may be switched once more, and Tate's body and Dixon's body may be used as well.

The fee is charged per switch, so the two of them need to know how few switches can finish the job before they quote a price. Given the switches the customers have already performed, find the minimum number of switches that puts every mind back into its own body.

The input consists of several test cases.

Each test case begins with a line holding two integers $N$ and $M$ separated by a space ($1 \le N \le 100{,}000$, $0 \le M \le 100{,}000$). $N$ is the number of customers, whose bodies are labelled $0, 1, 2, \dots, N-1$. Tate's body is $N$ and Dixon's body is $N+1$. $M$ is the number of switches the device has already performed.

The next line holds $2M$ integers separated by spaces.

$a_0,\ b_0,\ a_1,\ b_1,\ \dots,\ a_{M-1},\ b_{M-1}$

For each $j$ with $1 \le j \le M$, the $j$-th switch exchanged the minds held by bodies $a_{j-1}$ and $b_{j-1}$. Neither Tate nor Dixon took part in these switches, and the $M$ given pairs of bodies are all different.

The last line holds a single $0$. It is not a test case and must not be processed.

For each test case, print on one line the minimum number of switches needed to put every mind back into its own body. Print $0$ if every mind is already in place.