Даны два целых числа, \(n\) и \(k\). Рассмотрим граф на \(n\) вершинах, пронумерованных от \(1\) до \(n\), в котором изначально нет ребер.
Вам нужно назначить каждой вершине число; пусть \(a_i\) — число, назначенное вершине \(i\). Все \(a_i\) должны быть различными целыми числами от \(1\) до \(n\).
После того как вы назначили числа для вершин, вы добавляете в граф ребра. Для пары вершин \((i, j)\) добавляется ребро между ними, если \(|i - j| + |a_i - a_j| \le k\).
Ваша цель — создать граф, который можно разбить на минимально возможное (для заданных значений \(n\) и \(k\)) количество клик. Каждая вершина графа должна принадлежать ровно одной клике. Напомним, что клика — это такое множество вершин, что каждая пара вершин в этом множестве соединена ребром.
Поскольку BledDest не особо подтянул свои навыки программирования, он не может решить задачу «дан граф, разбейте его на минимальное количество клик». Поэтому мы также просим вас вывести само разбиение.
Выходные данные
Для каждого набора входных данных выведите три строки:
- первая строка должна содержать \(n\) различных целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)) — значения, которые вы назначаете вершинам;
- вторая строка должна содержать одно целое число \(q\) (\(1 \le q \le n\)) — количество клик, на которые вы разбиваете граф;
- третья строка должна содержать \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le q\)) — разбиение графа на клики. Где две вершины \(u\) и \(v\) в одной клике, если \(c_u = c_v\).
Если существует несколько ответов, выведите любой из них.