H. Лига покермонов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Добро пожаловать в мир покермонов, жёлтых мышеподобных существ, обожающих играть в покер!

Для распределения по покермонским лигам зарегистрировались n тренеров и существует t команд, каждая из которых должна быть определена в одну из конференций. Поскольку отношения между тренерами сильно натянутые, есть e пар тренеров, которые ненавидят друг друга. Отношение ненависти взаимно, все пары различны, никакой тренер не ненавидит сам себя. У каждого тренера есть список команд длиной li, в которые он хотел бы вступить.

Вам требуется распределить тренеров по командам и команды по конференциям таким образом, что выполнены следующие условия:

  • каждый тренер попадёт ровно в одну команду;
  • каждая команда будет только в одной конференции;
  • уровень ненависти между конференциями будет хотя бы e / 2;
  • каждый тренер будет в команде из своего списка.

Уровень ненависти между конференциями определяется как количество пар тренеров в командах из разных конференций, которые ненавидят друг друга.

Входные данные

В первой строке входных данных записаны два целых числа n (4 ≤ n ≤ 50 000) и e (2 ≤ e ≤ 100 000) — количество тренеров покермонов и количество пар тренеров, которые ненавидят друг друга.

Тренеры нумеруются от 1 до n. В последующих e строках даны пары целых чисел a и b (1 ≤ a, b ≤ n), означающих, что пара тренеров a и b ненавидит друг друга.

Следующие 2n строк описывают предпочтения тренеров в порядке от тренера 1 к тренеру n. Сначала следует число li (16 ≤ li ≤ 20) — количество команд в списке предпочтений данного тренера, затем li индексов команд ti, j (1 ≤ ti, j ≤ T) — номера команд, в которые хотел бы вступить данный тренер.

В списке одного тренера каждая команда встретиться не более одного раза. Команды в списках нумеруются таким образом, что каждое число из множества {1, 2, 3, …, T} встречается хотя бы один раз. Здесь T может быть до 1 000 000.

Выходные данные

Выведите две строки. В первой строке должно содержаться n чисел, определяющих в какую команду должен вступить каждый из тренеров. Во второй строке должно содержаться t чисел, определяющих к какой конференции должна принадлежать соответствующая команда (1 или 2).

Пример
Входные данные
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