퓨처라마

배경은 애니메이션 퓨처라마 시즌 6의 10화 The Prisoner of Benda다.

판스워스 교수가 만든 정신 교환 장치는 몸 두 개를 지정하면 그 안에 든 정신을 서로 바꿔 넣는다. 다만 설계 결함이 하나 있다. 이미 정신을 맞바꾼 몸 두 개에는 같은 장치를 다시 쓸 수 없다.

이 결함에서 장사가 하나 생겼다. 뒤엉킨 정신을 견디다 못한 손님 무리가 원래대로 돌려 달라고 부르면, 테이트와 딕슨이 자기 몸과 새 장치를 들고 온다. 새 장치에는 사용 기록이 없다. 그래서 복구 작업에서는 이미 교환에 쓰인 몸 짝도 다시 한 번 교환할 수 있고, 테이트와 딕슨의 몸을 끼워 넣어도 된다.

요금은 교환 한 번 단위로 붙는다. 그래서 두 사람은 견적을 내기 전에 최소 몇 번이면 끝나는지 알아야 한다. 손님이 지금까지 수행한 교환 기록이 주어질 때, 모든 정신을 원래 몸으로 되돌리는 데 필요한 교환의 최소 횟수를 구하라.

입력은 테스트 케이스 여러 개로 이루어진다.

각 테스트 케이스의 첫 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다 ($1 \le N \le 100{,}000$, $0 \le M \le 100{,}000$). $N$은 손님 수이고, 손님의 몸에는 $0, 1, 2, \dots, N-1$번이 붙어 있다. 테이트의 몸은 $N$번, 딕슨의 몸은 $N+1$번이다. $M$은 장치가 이미 수행한 교환 횟수다.

다음 줄에 정수 $2M$개가 공백으로 구분되어 주어진다.

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

$1 \le j \le M$인 $j$에 대해, $j$번째 교환에서 몸 $a_{j-1}$과 $b_{j-1}$에 든 정신이 서로 바뀌었다는 뜻이다. 이미 수행된 교환에는 테이트와 딕슨이 참여하지 않았고, 주어지는 몸 짝 $M$개는 모두 서로 다르다.

마지막 줄에는 $0$ 하나만 주어진다. 이 줄은 테스트 케이스가 아니므로 처리하지 않는다.

각 테스트 케이스마다 모든 정신을 원래 몸으로 되돌리는 데 필요한 교환의 최소 횟수를 한 줄에 출력한다. 이미 전부 제자리에 있으면 $0$을 출력한다.