$N$개의 정점과 $M$개의 간선으로 구성된 무방향 단순 연결 그래프가 주어진다.

그래프의 정점은 $1$부터 $N$까지의 정수로, 간선은 $1$부터 $M$까지의 정수로 번호가 매겨져 있다. 간선 $i$는 정점 $u_i$와 정점 $v_i$를 연결한다.

이 그래프는 다음과 같은 특별한 성질을 가진다: 모든 간선 $i$ ($1 \le i \le M$)에 대하여, 이 간선을 포함하지 않으면서 $u_i$와 $v_i$를 연결하는 경로가 존재한다. 이러한 경로를 간선 $i$의 우회 경로(bypass path)라고 부른다. 같은 간선에 대해 여러 개의 우회 경로가 존재할 수 있다.

우리는 $1$부터 $M$까지의 정수로 번호가 매겨진 색상을 사용하여 모든 간선에 정확히 하나의 색을 칠할 것이다. 어떤 색은 사용되지 않을 수도 있고, 어떤 색은 여러 번 사용될 수도 있다.

다음 성질을 만족하는 간선 색칠을 흥미로운 색칠(interesting coloring)이라고 한다:

• 공통 정점을 공유하는 두 간선은 서로 다른 색을 가진다.
• 모든 간선에 대하여, 특별한 우회 경로가 존재한다: 이는 8개 이하의 서로 다른 색으로 칠해진 간선들로 구성된 우회 경로를 의미한다.

당신의 과제는 흥미로운 색칠을 찾고, $M$개의 각 간선에 대하여 해당 간선의 특별한 우회 경로를 구성하는 데 사용할 수 있는 색상 집합을 출력하는 것이다.

위의 제약 조건 하에서 적어도 하나의 흥미로운 색칠이 존재함이 알려져 있다.

입력

입력의 첫 번째 줄에는 두 정수 $N$과 $M$ ($3 \le N \le 5555$, $3 \le M \le \min(N(N - 1)/2, 9999)$)이 주어진다. 이어지는 $M$개의 줄 중 $i$번째 줄은 $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$)로 시작해야 하며, 이는 목록에 포함된 색상의 개수이다. 그다음 $1$부터 $M$ 사이의 서로 다른 $k_i$개의 정수, 즉 색상 목록이 뒤따라야 한다. 색상은 어떤 순서로 출력해도 무방하다. 목록에 있는 색상 외의 다른 색을 사용하지 않으면서 $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

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)로 구성되므로 특별하다.