第一行有兩個非負整數$N,M\le {10}^5$且$N\ge 2$，分別代表球的個數以及烏龍複製的次數。
接下來的$M$行中每行有兩個相異正整數$i,j$，代表烏龍交換了編號$i$和編號$j$的兩顆球。

請輸出$M+1$行，每行代表小向至少需要交換幾次才能把球換回升序排列。
注意：你也需要輸出一開始的排列的答案。

「我…我悟出真理了！」小向愈使用念動力愈確信自己已學會如何控制魔力。
「一切的精髓都是『轉』啊！！！」
說完這句話，小向感覺到身上再度湧出魔力，和之前一樣。不同的是，這次她似乎能感覺到魔力的來源：一股來自臉部的兩處，一股來自身後……
正當小向覺得自己悟出真理時，結界忽然消失，烏龍倒了下去。
「欸！還好吧？」
「……看來我的力量也耗盡了……畢竟維持和原本世界的時間分流的結界本來就很耗體力……」
「欸欸，別睡啊！我們還得去森林的正中央呢！」
「……這個東西給你…它能引領你去森林的正中央……我想現在的我需要一點點的休息…」
烏龍的身體漸漸陷入土裡，似乎是為了要恢復魔力而進入類似「休眠」的狀態。
「現在的你…我相信現在的你…你已經獲得…凌駕於任何人的…強大魔力…」
烏龍留下這句話、小向以及給小向的神秘道具，完全陷入了土裡。

Problem Set / Description by Paupière