大型植被恢复

题目描述:

长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。

随着雨季即将到来，现在应当是重新种植的时候了。

在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。

他想要在每块草地上播种其中一种草。

作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。

他的 M 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。

已知每块草地最多被 3 头奶牛喜爱。

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

输入格式:

输入的第一行包含 N 和 M。

以下 M 行，每行包含两个范围为 1…N 的整数，为 Farmer John 的一头奶牛喜欢的两块草地。

输出格式:

输出一个 N 位数，每一位均为 1…4 之一，表示每一块草地上所种的草的种类。

第一位对应草地 1 的草的种类，第二位对应草地 2，以此类推。

如果有多种可行的解，只需输出所有解中最小的 N 位数。

数据范围:

2 ≤ N ≤ 100 ,
1 ≤ M ≤ 150

样例输入:

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

样例输出:

12133

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2019 February Contest Bronze