Start: Jun, 21, 2017 00:00:00
2017暑期短学期题库(part 4)
End: Jul, 05, 2017 12:00:00
Time elapsed:
Time remaining:

连鬼脚图 2048

Time Limit:  1 s      Memory Limit:   128 MB
Submission:28     AC:21     Score:1

Description

鬼脚图,又称画鬼脚,在日本称作阿弥陀签(あみだくじ),是一种游戏,也是一种简易决策方法,常被拿作抽签或者决定分配组合。

正因为鬼脚图的起点与终点为一一映射的关系,每个抽签的项目只有一个人会抽到,而且每个抽签的项目都一定会被抽到。所以当几个人要抽签决定一件事如何分配时,可以画鬼脚图决定。

首先画几条平行线,以平行线的一端为起点,另一端为终点,终点处写上抽签的项目。然后在相邻的纵线间任意画一些横线。最后每个人选一起点开始往下走,遇到横线则沿着横线走到隔壁的纵线,最后到达终点就是抽签所抽中的项目。 例如写上1、2、3、4、5组。这三条平行线之间任意画几条横行连线。开始时,由甲、乙、丙、丁、戊一端画起,遇到横线则打横跟着画去,遇上直线再向下跟着画下去,如此类推,最后就会神推鬼脚,去到1、2、3、4、5组任何一个作终点。再看起点和终点,便找出其各组的配对了。

Input

对每个样例

第一行为纵线条数w (w < 1024),

第二行为横线条数n (n < 1024),

接下来n行为用','分割的两个数字表示横线所连的两个端点

Output

输出w行

为从左到右的对应的数字

Samples

input
5 4 2,4 3,5 1,2 3,4
output
4 1 2 5 3

Hint

https://zh.wikipedia.org/zh-cn/%E9%AC%BC%E8%85%B3%E5%9C%96