建構生物個體之間的系統發育關係是生物資訊學中一項非常重要的工作。

系統發育關係通常用樹表示，稱為系統發育樹。每個個體對應系統發育樹中的一個葉節點。

系統發育樹中兩個葉節點之間的路徑長度，表示對應的兩個個體在演化上的親近程度。

利用系統發育樹，可以定義一個圖，表示各個體在演化上的親近程度。

這個圖稱為系統發育圖。

相似度為 $K$ 的系統發育圖定義如下。

圖的每個頂點表示一個個體。兩個頂點之間存在邊，若且唯若系統發育樹中與這兩個頂點對應的節點之間的距離（路徑長度）不超過 $K$。

某實驗室建構了相似度為 $3$ 的系統發育圖之後，遺失了系統發育樹的資料。因此，現在要進行復原系統發育樹的工作。

給定一個相似度為 $3$ 的系統發育圖，編寫程式求出一棵定義該圖的系統發育樹。

注意，輸入的系統發育圖總是連通的，並且保證存在對應的系統發育樹。

輸入格式

第一行給出一個整數 $N$（$2 \le N \le 5000$），表示系統發育圖的頂點數。

頂點編號為 $1$ 到 $N$。

第二行給出一個整數 $M$（$1 \le M \le 1000000$），表示系統發育圖的邊數。

接下來的 $M$ 行，每行給出兩個整數 $v,w$（$1 \le v,w \le N$），表示系統發育圖中一條邊的兩個端點編號。

輸出格式

第一行輸出系統發育樹的邊數 $S$。

接下來的 $S$ 行，每行輸出一條邊的兩個端點編號 $v$、$w$，中間以一個空格分隔。

樹的邊可以按任意順序輸出。

但樹中編號 $1$ 到 $N$ 必須分配給葉節點。

另外，輸入系統發育圖中的頂點，與系統發育樹中對應的葉節點，必須使用相同的編號。

其餘內部節點可以任意使用 $N+1$ 到 $S+1$ 的編號。如果存在多棵系統發育樹，只需求出並輸出其中任意一棵。

範例

輸入格式 1

6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3

輸出格式 1

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

所有測試通過得 100 分，否則得 0 分。