Дан неориентированный простой связный граф, состоящий из $N$ вершин и $M$ ребер.

Вершины графа пронумерованы последовательными целыми числами от 1 до $N$, а ребра пронумерованы последовательными целыми числами от 1 до $M$. Ребро $i$ соединяет вершину $u_i$ и вершину $v_i$.

Для этого графа выполняется следующее особое свойство: для каждого ребра $i$ ($1 \le i \le M$) существует путь, соединяющий $u_i$ и $v_i$, который не содержит этого ребра. Мы будем называть такой путь обходным путем (bypass path) для ребра $i$. Для одного и того же ребра может существовать более одного обходного пути.

Мы раскрасим ребра в цвета, пронумерованные последовательными целыми числами от 1 до $M$, присвоив ровно один цвет каждому ребру. Некоторые цвета могут остаться неиспользованными, другие могут быть использованы более одного раза.

Раскраска ребер называется интересной, если выполняются следующие свойства: Если два ребра имеют общую вершину, их цвета различны. Для каждого ребра существует специальный обходной путь: обходной путь, содержащий ребра, раскрашенные не более чем в 8 различных цветов.

Ваша задача — найти интересную раскраску и для каждого из $M$ ребер вывести любой набор цветов, который можно использовать для построения специального обходного пути для этого ребра.

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

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

Первая строка входных данных содержит два целых числа $N$ и $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$). $i$-я из следующих $M$ строк описывает $i$-е ребро и содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i < v_i \le N$).

Вы можете считать, что каждая пара $(u, v)$ встречается в списке не более одного раза, что данный граф связен и что после удаления любого ребра $(u, v)$ все еще существует обходной путь, соединяющий $u$ и $v$.

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

Выведите любую интересную раскраску в следующем формате. В первой строке выведите $M$ целых чисел. $i$-е из этих чисел, $C_i$, должно быть цветом $i$-го ребра ($1 \le C_i \le M$).

Затем выведите $M$ строк. $i$-я из этих строк описывает набор цветов специального обходного пути для ребра $i$. Эта строка должна начинаться с целого числа $k_i$ ($1 \le k_i \le 8$): количества цветов в списке. Далее должны следовать $k_i$ попарно различных целых чисел от 1 до $M$: список цветов. Цвета можно выводить в любом порядке. Должен существовать специальный обходной путь между $u_i$ и $v_i$, который не использует никаких цветов, кроме цветов из списка. Обратите внимание, что это означает, что список цветов не обязан быть минимально возможным, и может существовать путь, использующий лишь часть списка: проверяющая программа лишь убеждается, что указанных цветов достаточно.

Примеры

Пример 1

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
1 4

1 2 3 4 5 6 7 8 9 10 5
3 2 3 5
3 1 3 5
3 1 2 5
6 5 6 7 8 9 10
7 4 5 6 7 8 9 10
6 4 5 7 8 9 10
6 4 5 6 8 9 10
6 4 5 6 7 9 10
6 4 5 6 7 8 10
8 4 5 6 7 8 9 1 2
3 1 2 3

Примечание

В примере для первого ребра есть два обходных пути. Более длинный содержит 9 цветов (от 2 до 10), поэтому он не является специальным. Более короткий состоит из ребер 2, 3 и 11 (цвета 2, 3 и 5), поэтому он является специальным.