← 返回题目列表

Codeforces · 357/B

B. 卖旗日

中文机器翻译题面 查看原题

在伯兰,国庆节即将到来——卖旗日。为了纪念这一活动,该国总统决定举办一场大型舞会,并请贵机构组织。他有几个条件:

- 总共必须有 m 支舞蹈;
- 每支舞蹈必须由三人参加;
- 每支舞蹈必须有一名白色衣服的舞者、一名红色衣服的舞者和一名蓝色衣服的舞者(这些是贝尔兰国旗的颜色)。

该机构有n个舞者,其数量可以小于3m。也就是说,一些舞者可能不得不跳不止一种舞蹈。所有舞者都必须在派对上跳舞。然而,如果某个舞蹈有两个或更多来自前一个舞蹈的舞者,那么当前的舞蹈就不再引人注目。您的机构不能允许这种情况发生,因此每个舞蹈最多有一名曾参加过之前舞蹈的舞者。

您考虑了所有标准并制定了 m 支舞蹈的计划:每支舞蹈有 3 名舞者参加。你的任务是确定n个舞者每人的衣服颜色,以便满足总统的第三个条件:每个舞蹈必须有一个白色的舞者,一个红色的舞者和一个蓝色的舞者。舞者在舞蹈之间不能更换衣服。

输入

第一行包含两个空格分隔的整数 n (3 ≤ n ≤ 105) 和 m (1 ≤ m ≤ 105) — 相应地,舞者数量和舞蹈数量。接下来是 m 行,按照跳舞的顺序描述舞蹈。第 i 行包含三个不同的整数——参加第 i 场舞蹈的舞者数量。舞者的编号为 1 到 n。每个舞者至少参加一支舞蹈。

输出

打印n个空格分隔的整数:第i个数字必须代表第i个舞者的衣服颜色(1代表白色,2代表红色,3代表蓝色)。如果有多个有效的解决方案,请打印其中任何一个。保证至少存在一个解。

示例

输入 #1

7 3
1 2 3
1 4 5
4 6 7

输出 #1

1 2 3 3 2 2 1

输入 #2

9 3
3 6 9
2 5 8
1 4 7

输出 #2

1 1 1 2 2 2 3 3 3

输入 #3

5 2
4 1 5
3 1 2

输出 #3

2 3 1 1 3