Problem1890--普及组模拟赛一B换糖游戏

1890: 普及组模拟赛一B换糖游戏

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit
Solved: 1Submit Num: 1Statistics

Description

Homer看着手上的英语试卷，想起了六一时玩的换糖游戏。
游戏规则是这样的：
    游戏中有n颗糖排成 1 排，它们的编号从左到右为 1~ n。
    现在我们规定m 对位置上的糖果是可以交换的，并且可以交换多次。
    最终率先说出这n颗糖果通过交换可以得到的编号的最大字典序的同学获胜 。
现在Homer想知道，在糖果数n以及可交换的m对糖果的位置确定时，交换后糖果编号的字典序最大是多少。

Input

 第一行有两个整数n和m表示糖果数目和可交换的糖果对数。
 接下来n行每行两个整数xi和yi表示每对可交换糖果的位置

Output

 共一行，有 n个数字，表示最大字典序

Sample Input Copy 

5 3
2 3
2 5
1 4

Sample Output Copy 

4 5 3 1 2

HINT

数据范围
    对于30%的数据，n,m<=100
    对于60%的数据，n,m<=10000
    对于100%的数据，n,m<=1000000  xi,yi<=n

Source/Category

模拟赛 
Submit