TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Description

有 $n$ 個人，他們各為自己國家的元首，編號 $1$~$n$，有 $q$ 次操作。
操作 1：$a$ 國吞并了 $b$ 國，並且 $a$ 成為新國度的元首。（保證 $a$、$b$ 都是元首）
操作 2：請輸出以 $x$ 為首的國家有多少人（若 $x$ 非元首則輸出 $-1$）。
最後請輸出剩下的每個國家的元首跟成員組合。

Input Format

第一行包含兩個正整數 $n$, $q$ 以空白隔開，代表有 $n$ 個人，接下來有 $q$ 次操作。
第 $2$ 行至第 $q+1$ 行，每行有可能為:

1 a b 代表操作 $1$
2 x 代表操作 $2$

$n, q \le 10^ 5$
$1 \le a,b,x \le n$

Output Format

對於每個操作 2，輸出一個整數並換行
最後請由小到大輸出剩下的每個國家的元首跟成員組合。
每一行請輸出 x_i: y_1 y_2 y_3...
代表該國家的元首為 $x_i$，成員組合為 $y_1,\ y_2,\ \dots$
請由小到大輸出國家元首，再由小到大輸出其成員組合（包含元首）。

Sample Input 1

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

Sample Output 1

3
-1
1: 1 2 5
4: 3 4

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~15	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2

652 . 共主邦聯