TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

96.6% (28/29)

Submission's AC Ratio

51.1% (95/186)

Tags

Description

你聽過中國洗衣問題(又稱中國烘衣問題)嗎?如果不知道,請繼續看下去。

中國人對於洗烘衣這件事有非常獨到的見解。對中國人來說,洗衣和烘衣是兩件等價的事情,所以當然洗衣機和烘衣機也是等價的。因此存在這個一個傳說:從前從前,有個中國人想要乾洗,於是就把衣服丟進烘衣機裡,灑了洗衣粉進去,就啟動了烘衣機。
另外,中國人也會習慣性地把兩臺洗衣機裡面的衣服互換,也有一套祖傳的交換規則,以讓他們能互相分享好衣服。因此,就算洗完一次衣服可以拿回來的衣服比例期望值是77%(也就是洗一次衣服,平均大約五件中會損失一件),他們也不以為意。

你,身處在魔法座標系(通常稱為L6DML)上(303.34, 2768.97)這個位置,只是個想洗衣服的人,等待N臺洗衣機之中的其中一臺結束。然而,當你終於排到隊把衣服放下去洗,等待了35洗衣機分鐘(相當於SI制的60*70秒),準備拿衣服的時候,卻發現在這段時間內,來過了不知道幾個中國人,把所有洗衣機裡面的衣服大洗牌(我們稱這個現象為「洗衣」),而且還有一個中國人C正要開始交換衣服。

你是個見義勇為的人,雖然你知道你的衣服在哪裡,但是為了讓其他人能夠在原本的洗衣機裡拿到他的衣服,你決定把所有衣服搬回它原本所在的那臺洗衣機。你知道洗衣機和衣服都從0號編到N-1號,並且x號衣服原本在x號洗衣機裡;你也知道在被中國人「洗衣」之後,每一臺洗衣機裡面是幾號衣服。

因為你以前曾經得到中國人的祖傳秘方,所以你知道中國人的交換衣服的規則是:他們有一個長度為M的數對序列<(__, __)>(也許兩個空格應該分別填入Ai和Bi吧),當他們要交換第i次衣服時就會把編號為Ai和Bi的洗衣機裡面的衣服交換。
(注意有可能Ai=Bi,如此中國人就會把這臺洗衣機裡面的衣服拿出來再放進去,這樣也算是一次交換。)

當你反應過來時,中國人C已經做了第0次交換。你知道中國人C兩次交換衣服之間的時間只剛好夠你做一次交換,所以你決定要和中國人C輪流交換衣服。你知道只要在你交換完之後,所有的衣服已經在原本的洗衣機裡面,中國人C就會自己離開。
(同樣的,你也可以選擇把衣服拿出來再放進去。)

你的任務就是求出你總共要幾次可以把衣服換到正確位置,以及決定每一次要交換哪兩個洗衣機的衣服。你最多只能做M次交換,不然就會有更多中國人來打亂你的交換了。

Input Format

第一行有一個數字T,代表你總共遇到這個事件幾次。

對於每一個事件:
第一行有一個數字N,代表總共有幾臺洗衣機。
第二行有N個數字Si,代表在中國人C進行第0次交換之前,第i號洗衣機裡面是第Si號衣服。
第三行有一個數字M,代表中國人C的祖傳序列長度,也代表你最多可以做幾次交換。
接下來有M行,每行有兩個整數Ai, Bi,代表中國人的祖傳序列。

對於8%的測資,N<=5,且每次中國人C都會把0號洗衣機的衣服拿出來再放進去。M = N2
對於12%的測資,N<=100,且每次中國人C都會把0號洗衣機的衣服拿出來再放進去。M = 30N。
對於16%的測資,N<=100,且每次中國人C都會把0號和1號洗衣機裡的衣服交換。M = 30N。
對於18%的測資,N<=500。M = 30N。
對於20%的測資,N<=2000。M = 3N。你必須在最少的交換次數內把衣服歸位。
對於26%的測資,N<=200000。M = 3N。你必須在最少的交換次數內把衣服歸位。

Output Format

對於每一筆測資,請輸出P+1行,代表你的交換衣服策略。
第一行有一個數字P,代表你要交換幾次;接下來P行,每行有兩個數字Ci, Di,代表每一次你要交換哪兩個洗衣機裡面的衣服。

Sample Input

2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2

Sample Output

3
1 4
2 4
2 2
3
0 4
1 3
3 4

Hints

Problem Source

IOI 2015 Day 2
Problem set / Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 18
For Testdata: 4 ~ 4, Score: 20
For Testdata: 5 ~ 7, Score: 26
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 14000 262144 65536
5 9000 262144 65536
6 8000 262144 65536
7 8000 262144 65536