TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

41.4% (41/99)

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

5 3
1 4 2 5 3
1 2
3 4
4 5

Sample Output

3
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4
20 1000 65536 262144 5
21 1000 65536 262144 5
22 1000 65536 262144 5
23 1000 65536 262144 5
24 1000 65536 262144 5