Длительная засуха лишила травы \(N\) пастбищ Фермера Джона.
Однако с приближением сезона дождей пришло время восстановить траву
на пастбищах.
В сарае ФД есть четыре ведра, каждое хранит семена своего типа.
ФД хочет посадить на каждом пастбище траву семенами одного из этих типов.
ФД хочет каждой их своей коров различную диету. Каждая из его \(M\) коров
имеет два любимых пастбища. И он хочет гарантировать, чтобы на каждой
такой паре пастбищ была засеяна трава различных типов, и тогда каждая
корова сможет выбирать из двух видов травы. ФД знает, что нет пастбища,
которое нравится более чем трём коровам.
Помогите ФД выбрать тип травы для каждого пастбища так, чтобы запросы
по питанию всех коровы были удовлетворены.
ФОРМАТ ВВОДА (файл revegetate.in):
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 100\)) и \(M\)
(\(1 \leq M \leq 150\)).
Каждая из последующих \(M\) строк содержит два целых числа в интервале
\(1 \ldots N\), описывающих пару любимых пастбищ соответствующей коровы.
ФОРМАТ ВЫВОДА (файл revegetate.out):
Выведите число из N цифр, каждая цифра которого в интервале \(1 \ldots 4\),
описывающее тип травы, которую нужно посадить на соответствующем пастбище.
Первая цифра описывает тип травы на пастбище 1, вторая - на пастбище 2 и т.д.
Если возможно несколько решений, выведите такое, что соответствующее число из
\(N\) цифр минимальное.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6
4 1
4 2
4 3
2 5
1 2
1 5
|
12133
|