1950 . 小向的試煉 2-3：轉！(Rotate!)
TopCoder
Tags
Description
「現在我們在的這個結界是與流動的時間分離的虛無縹渺的空間」烏龍唸了一長串咒文，展開結界後，為疑惑的小向解釋了一下現在的狀況。
「總之，要練習控制魔力，最好的方法就是練習念動力了。」
念動力，顧名思義就是…額其實大家都知道對不對…
「現在有$N$顆球，編號1到$N$。而你需要用念動力把$N$顆球換回原位。」烏龍邊拿出$N$顆球邊解釋。
「不過千萬記得，小心控制魔力，別像這個女孩一樣魔力失控了。」
雖然是訓練，不過小向還是希望用最少次的步數換回去。烏龍注意到了這點。
「欸欸欸，有必要這樣嗎…」烏龍搖搖頭，覺得小向真的是太偷懶了。
「既然這樣，我就跟著換球吧…」
於是烏龍就把目前的$N$顆球複製了一次，然後再把其中兩顆球交換，接著再複製交換後的結果，再把其中兩顆球交換，如此地出了$M$道題目。
「這樣應該就不能偷懶了吧小向。」
「烏龍你太天真了……」小向使出秘藏的魔法，一次算出了所有答案……
Input Format
第一行有兩個非負整數$N,M\leq 10^ 5$且$N\geq 2$，分別代表球的個數以及烏龍複製的次數。
接下來的$M$行中每行有兩個相異正整數$i,j$，代表烏龍交換了編號$i$和編號$j$的兩顆球。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $M=0$ | 8 |
| 2 (5~9) | $M=1$ | 12 |
| 3 (10~14) | $M,N\leq 10^ 4$ | 12 |
| 4 (15~19) | $i,j,M\leq 10^ 4$ | 24 |
| 5 (20~24) | 無 | 44 |
Output Format
請輸出$M+1$行，每行代表小向至少需要交換幾次才能把球換回升序排列。
注意：你也需要輸出一開始的排列的答案。
Sample Input 1
1 4 2 5 3
1 2
3 4
4 5
Sample Output 1
4
3
2
Hints
「我…我悟出真理了！」小向愈使用念動力愈確信自己已學會如何控制魔力。
「一切的精髓都是『轉』啊！！！」
說完這句話，小向感覺到身上再度湧出魔力，和之前一樣。不同的是，這次她似乎能感覺到魔力的來源：一股來自臉部的兩處，一股來自身後……
正當小向覺得自己悟出真理時，結界忽然消失，烏龍倒了下去。
「欸！還好吧？」
「……看來我的力量也耗盡了……畢竟維持和原本世界的時間分流的結界本來就很耗體力……」
「欸欸，別睡啊！我們還得去森林的正中央呢！」
「……這個東西給你…它能引領你去森林的正中央……我想現在的我需要一點點的休息…」
烏龍的身體漸漸陷入土裡，似乎是為了要恢復魔力而進入類似「休眠」的狀態。
「現在的你…我相信現在的你…你已經獲得…凌駕於任何人的…強大魔力…」
烏龍留下這句話、小向以及給小向的神秘道具，完全陷入了土裡。
Problem Source
Problem Set / Description by Paupière
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 8 |
| 2 | 5~9 | 12 |
| 3 | 10~14 | 12 |
| 4 | 15~19 | 24 |
| 5 | 20~24 | 44 |