TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

75.0% (18/24)

Submission's AC Ratio

44.8% (82/183)

Tags

Description

$p_0,p_1,\cdots,p_{M-1}$ 是 $M$ 個 $1 \sim N$ 的排列,且對於 $i = 1, 2, 3, \cdots, M-1$ ,$p_i$ 是 $p_{i-1}$ 交換第 $x_i$ 和第 $y_i$ 個數字得到的排列。假設依照字典序排序這 $M$ 個排列後我們有 $p_{a_1} \le p_{a_2} \le \cdots \le p_{a_M}$(若有一樣的排列,則讓下標較小的排列出現在前面),請輸出 $a_1, a_2,\cdots,a_M$。

Input Format

輸入第一行有兩個正整數分別代表 $N$ 和 $M$。
下一行有 $N$ 個數字代表 $p_0$。
接著 $M-1$ 行中每行有兩個正整數,其中第 $i$ 行的兩個正整數代表 $x_i, y_i$。

Output Format

輸出只有一行包含 $M$ 個以空白分隔的整數 $a_1, a_2,\cdots, a_M$。

Sample Input 1

3 4
3 1 2
1 2
1 3
2 3

Sample Output 1

1 3 2 0

Sample Input 2

2 3
1 2
1 2
1 2

Sample Output 2

0 2 1

Hints

範例測試一中,$p_0 = [3, 1, 2], x = [1, 1, 2], y = [2, 3, 3]$,將 $p_0$ 的第一個數字($x_1 = 1$)和第二個數字($y_1 = 2$)交換,得到 $p_1 = [1, 3, 2]$, 接著把 $p_1$ 的第一個數字和第三個數字交換,得到 $p_2 = [2, 3, 1]$,最後類似的得到 $p_3 = [2, 1, 3]$。經過字典序比較後我們知道 $p_1 < p_3 < p_2 < p_0$,所以照順序輸出 $1, 3, 2, 0$ 四個數字。

範例測試二中, $p_0 = [1,2], p_1 = [2,1], p_2 = [1,2]$,注意到 $p_0$ 和 $p_2$ 是一樣的排列,所以我們將 $p_0$ 排到 $p_2$ 前面,也就是 $p_0 \le p_2 \le p_1$,所以輸出$0,2,1$三個數字。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~34 $N, M \leq 10^ 5$ 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 256000 65536 1
1 1000 256000 65536 1
2 1000 256000 65536 1
3 1000 256000 65536 1
4 1000 256000 65536 1
5 1000 256000 65536 1
6 1000 256000 65536 1
7 1000 256000 65536 1
8 1000 256000 65536 1
9 1000 256000 65536 1
10 1000 256000 65536 1
11 1000 256000 65536 1
12 1000 256000 65536 1
13 1000 256000 65536 1
14 1000 256000 65536 1
15 1000 256000 65536 1
16 1000 256000 65536 1
17 1000 256000 65536 1
18 1000 256000 65536 1
19 1000 256000 65536 1
20 3000 256000 65536 1
21 3000 256000 65536 1
22 3000 256000 65536 1
23 3000 256000 65536 1
24 3000 256000 65536 1
25 3000 256000 65536 1
26 3000 256000 65536 1
27 3000 256000 65536 1
28 3000 256000 65536 1
29 3000 256000 65536 1
30 3000 256000 65536 1
31 3000 256000 65536 1
32 3000 256000 65536 1
33 3000 256000 65536 1
34 3000 256000 65536 1