Пете Годунову приказали составить карту Сибири, которая состоит из n волостей, некоторые из которых причудливым образом граничат друг с другом. Он хотел бы раскрасить каждую в какой-нибудь цвет, но у него есть только k различных красок. Кроме того, согласно техническому заданию, на окончательном варианте карты две волости должны быть разного цвета тогда и только тогда, когда они являются соседними. Использовать при этом все краски вовсе не обязательно. Помогите Пете справиться с задачей, иначе начальство отрубит ему голову.
В первой строке содержатся три целых числа через пробел: n, m и k (1 ≤ n ≤ 1000, 
, 1 ≤ k ≤ n) — количество волостей в Сибири, количество пар соседних волостей и количество красок у Пети соответственно.
Далее в m строках содержатся по два целых числа через пробел: xj и yj (1 ≤ xj, yj ≤ n, xj ≠ yj) — номера соседних волостей. Каждая пара волостей встречается не более одного раза.
Выведите n целых чисел ci через пробел (1 ≤ ci ≤ k), где ci — это цвет, в который нужно покрасить i-ую волость. Если Пете не сносить головы, выведите единственное число « - 1».
3 2 2
1 2
2 3
1 2 1
4 4 2
1 2
2 3
3 4
4 1
1 2 1 2
4 4 3
1 2
1 3
1 4
2 3
-1
