Q1
```
有n颗珍珠，编号为1至n，爸爸和小明做游戏，让小明把这些珍珠串成若干串项链。初始时n颗珍珠摆放在桌子上，每颗珍珠自成一个项链（即相当于有n个项链，每个项链只含一颗珍珠）。

每次爸爸让小明做如下操作“a b”，表示将珍珠a所在的项链串在珍珠b所在的项链后面，形成一串新的项链，即a所在项链的第一个珍珠排在b所在项链的最后一个珍珠后面，如果珍珠a和b已在同一项链里，则忽略该操作。

请编写程序，输出小明完成爸爸的所有操作后，每个珍珠所在的项链的链头（该项链第一颗珍珠的编号）。

输入格式:
每个测试点包含多组测试数据，第一行1个整数 T ，表示测试数据组数。对于每组数据，第一行两个整数 n 和 m，分别表示珍珠个数和操作次数。接下来 m 行，每行两个整数a和b，表示爸爸让小明执行的一个操作。T≤5，1≤n, m≤30000，1≤a, b≤n。

输出格式:
输出为T 行，每行为 n个整数a 
1
​
 a 
2
​
 …a 
n
​
 ，每个整数后一个空格，a 
i
​
 (1≤i≤n)表示珍珠i所在项链的链头珍珠编号。

输入样例:
2
4 2
2 1
4 3
5 4
1 2
2 3
4 5
1 3


输出样例:
1 1 3 3 
3 3 3 5 5 

数据规模:
测试点0：1 ≤n, m ≤ 10；
测试点1：10 < n, m ≤100；
测试点2：100 < n, m ≤ 1000；
测试点3：1000 < n, m ≤10000；
测试点4：10000 < n, m ≤ 30000。

代码长度限制
16 KB
时间限制
100 ms
内存限制
64 MB
栈限制
8192 KB
```

Q2
```
编写程序统计一棵非空二叉树中每层度为1的结点的数目，二叉树结点个数不超过100。

输入格式:
输入为一个字符串，表示带空指针信息的二叉树先根序列。其中空指针信息用#表示，二叉树结点为a-z, A-Z的字母。

输出格式:
输出为若干行，按层数从小到大次序输出二叉树每层度为1的结点个数，即第1行输出第0层度为1的结点个数，第2行输出第1层度为1的结点个数，以此类推。

输入样例:
ABD###CE###
输出样例:
0
2
0
代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
栈限制
8192 KB
```

Q3
```
编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：

选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为cba，三个字母均出现1次，但c在文本中最先出现，b第二出现，故则选择c作为左子树，b作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
生成哈夫曼编码时，哈夫曼树左分支标记为0，右分支标记为1。
输入格式:
输入为3行。第1行为一个字符串，包含不超过5000个字符，至少包含两个不同的字符，每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串，表示待译码的哈夫曼编码。

输出格式:
输出第一行为用空格间隔的2个整数，分别为压缩前后文本大小，以字节为单位，一个字符占1字节，8个二进制位占1字节，若压缩后文本不足8位，则按1字节算。输出从第二行开始，每行为1个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出INVALID。

输入样例:
cbaxyyzz
0100
011

输出样例:
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

代码长度限制
16 KB
时间限制
50 ms
内存限制
64 MB
栈限制
8192 KB
```