The Great Revegetation

题目描述

一场漫长的干旱使得 Farmer John 的 $N$ 块牧场都没有了草。不过，雨季即将到来，是时候重新“植被恢复”了。

在 Farmer John 的棚子里，他有四个桶，每个桶里装着不同种类的草籽。他希望给每块牧场播种其中一种草籽。作为一名奶牛场主，Farmer John 想确保每头奶牛的饮食多样。

他的每头 $M$ 头奶牛都有两块最喜欢的牧场，他希望确保这两块牧场种植不同种类的草，这样每头奶牛就能在两种草之间做选择。Farmer John 知道，没有任何一块牧场会成为超过 $3$ 头奶牛的最爱。

请帮助 Farmer John 为每块牧场选择一种草的类型，使得所有奶牛的营养需求都得到满足。

输入格式

第一行输入包含 $N$（$2 \leq N \leq 100$）和 $M$（$1 \leq M \leq 150$）。 接下来的 $M$ 行每行包含两个范围在 $1 \ldots N$ 的整数，描述 Farmer John 的一头奶牛最喜欢的两块牧场的编号。

输出格式

输出一个 $N$ 位数字串，每一位数字的范围为 $1 \ldots 4$，表示每块田要种植的草的类型。第 1 位对应第 $1$ 块田的草种类型，第 2 位对应第 $2$ 块田的草种类型，依此类推。 如果存在多种可行方案，只输出其中按数值比较最小的那一个 $N$ 位数字串。

5 6
4 1
4 2
4 3
2 5
1 2
1 5

12133

提示

题目鸣谢：Dhruv Rohatgi

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze