编程题：珍珠项链

有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$$所在项链的链头珍珠编号。


### 输入样例:

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




### 输出样例:

out
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。






答案：若无答案欢迎评论