Добро пожаловать в мир покермонов, жёлтых мышеподобных существ, обожающих играть в покер!
Для распределения по покермонским лигам зарегистрировались n тренеров и существует t команд, каждая из которых должна быть определена в одну из конференций. Поскольку отношения между тренерами сильно натянутые, есть e пар тренеров, которые ненавидят друг друга. Отношение ненависти взаимно, все пары различны, никакой тренер не ненавидит сам себя. У каждого тренера есть список команд длиной li, в которые он хотел бы вступить.
Вам требуется распределить тренеров по командам и команды по конференциям таким образом, что выполнены следующие условия:
- каждый тренер попадёт ровно в одну команду;
- каждая команда будет только в одной конференции;
- уровень ненависти между конференциями будет хотя бы e / 2;
- каждый тренер будет в команде из своего списка.
Уровень ненависти между конференциями определяется как количество пар тренеров в командах из разных конференций, которые ненавидят друг друга.
Выходные данные
Выведите две строки. В первой строке должно содержаться n чисел, определяющих в какую команду должен вступить каждый из тренеров. Во второй строке должно содержаться t чисел, определяющих к какой конференции должна принадлежать соответствующая команда (1 или 2).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2
2 3
4 1
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 15
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 18
16
2 3 4 5 6 7 8 9 10 11 12 13 14 15 18 19
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 19
|
16 15 19 14
2 2 2 1 1 1 2 1 1 2 1 1 1 2 2 1 1 1 1
|