給定一個包含 $n$ 個頂點與 $m$ 條邊的無向圖。 你可以執行以下操作至多 $2 \cdot \max(n, m)$ 次：

• 選擇三個相異的頂點 $a, b, c$，然後對於邊 $(a, b)$、$(b, c)$ 與 $(c, a)$ 中的每一條，執行以下動作：
  • 如果該邊不存在，則加入它。反之，如果該邊存在，則移除它。

若一個圖滿足以下任一條件，則稱其為「酷」（cool）：

• 該圖沒有邊，或
• 該圖是一棵樹。

你必須透過執行上述操作使圖變為「酷」。請注意，你最多可以使用 $2 \cdot \max(n, m)$ 次操作。 可以證明至少存在一個解。

輸入格式

每個測試包含多個測試案例。第一行包含一個整數 $t$ ($1 \le t \le 10^4$)，代表測試案例的數量。接著是各個測試案例的描述。

每個測試案例的第一行包含兩個整數 $n$ 與 $m$ ($3 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$)，分別代表頂點數量與邊的數量。

接下來 $m$ 行，第 $i$ 行包含兩個整數 $u_i$ 與 $v_i$ ($1 \le u_i, v_i \le n$)，代表第 $i$ 條邊連接的兩個節點。

保證所有測試案例的 $n$ 之總和不超過 $10^5$，且所有測試案例的 $m$ 之總和不超過 $2 \cdot 10^5$。 保證給定的圖中沒有自環或重邊。

輸出格式

對於每個測試案例，第一行輸出一個整數 $k$ ($0 \le k \le 2 \cdot \max(n, m)$)，代表操作次數。 接著輸出 $k$ 行，第 $i$ 行包含三個相異的整數 $a, b, c$ ($1 \le a, b, c \le n$)，代表你在第 $i$ 次操作中選擇的三個頂點。

若有多種解，輸出其中任意一種即可。

範例

輸入格式 1

5
3 0
3 1
1 2
3 2
1 2
2 3
3 3
1 2
2 3
3 1
6 6
1 2
1 6
4 5
3 4
4 6
3 6

輸出格式 1

0
1
1 2 3
0
1
1 2 3
3
1 3 6
2 4 5
3 4 6

說明

在第一個測試案例中，該圖已經是「酷」的，因為它沒有邊。 在第二個測試案例中，執行唯一的操作後，圖變成了一棵樹，因此它是「酷」的。 在第三個測試案例中，該圖已經是「酷」的，因為它是一棵樹。 在第四個測試案例中，執行唯一的操作後，圖沒有邊，因此它是「酷」的。 在第五個測試案例中：

操作 1：操作前的圖

操作 1：操作後的圖

操作 2：操作前的圖

操作 2：操作後的圖

操作 3：操作前的圖

操作 3：操作後的圖

請注意，在第一次操作後，圖已經變為「酷」的，而後續還有兩次額外操作。由於在兩次額外操作後圖仍然是「酷」的，這是一個有效的答案。