給定一個包含 $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）：

• 若兩條邊共用一個頂點，則它們的顏色必須不同。
• 對於每一條邊，皆存在一條「特殊繞道」：該繞道所包含的邊，其顏色種類不超過 $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$) 開頭，代表列表中顏色的數量。隨後必須跟隨 $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

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$），因此它是特殊的。