Bạn được cho một đồ thị vô hướng với $n$ đỉnh và $m$ cạnh. Bạn có thể thực hiện thao tác sau tối đa $2 \cdot \max(n, m)$ lần:

• Chọn ba đỉnh phân biệt $a, b$ và $c$, sau đó với mỗi cạnh $(a, b), (b, c)$ và $(c, a)$, thực hiện như sau:
  • Nếu cạnh không tồn tại, hãy thêm nó vào. Ngược lại, nếu nó đã tồn tại, hãy loại bỏ nó.

Một đồ thị được gọi là cool nếu và chỉ nếu một trong các điều kiện sau thỏa mãn: Đồ thị không có cạnh nào, hoặc Đồ thị là một cây.

Bạn cần làm cho đồ thị trở nên cool bằng cách thực hiện các thao tác trên. Lưu ý rằng bạn có thể sử dụng tối đa $2 \cdot \max(n, m)$ thao tác. Có thể chứng minh rằng luôn tồn tại ít nhất một lời giải.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 10^4$) — số lượng bộ dữ liệu. Mô tả các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($3 \le n \le 10^5$, $0 \le m \le \min\left(\frac{n(n-1)}{2}, 2 \cdot 10^5\right)$) — số lượng đỉnh và số lượng cạnh.

Tiếp theo là $m$ dòng, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$) — hai nút mà cạnh thứ $i$ kết nối.

Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$, và tổng $m$ trên tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Đảm bảo rằng không có khuyên (self-loop) hoặc đa cạnh trong đồ thị đã cho.

Dữ liệu ra

Với mỗi bộ dữ liệu, ở dòng đầu tiên, hãy in ra một số nguyên $k$ ($0 \le k \le 2 \cdot \max(n, m)$) — số lượng thao tác.

Sau đó in ra $k$ dòng, dòng thứ $i$ chứa ba số nguyên phân biệt $a, b$ và $c$ ($1 \le a, b, c \le n$) — ba số nguyên bạn chọn trong thao tác thứ $i$.

Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Ghi chú

Trong bộ dữ liệu đầu tiên, đồ thị đã cool vì không có cạnh nào.

Trong bộ dữ liệu thứ hai, sau khi thực hiện thao tác duy nhất, đồ thị trở thành một cây, vì vậy nó là cool.

Trong bộ dữ liệu thứ ba, đồ thị đã cool vì nó là một cây.

Trong bộ dữ liệu thứ tư, sau khi thực hiện thao tác duy nhất, đồ thị không còn cạnh nào, vì vậy nó là cool.

Trong bộ dữ liệu thứ năm:

Thao tác 1: Đồ thị trước thao tác

Lưu ý rằng sau thao tác đầu tiên, đồ thị đã trở nên cool, và có hai thao tác thừa. Vì đồ thị vẫn cool sau hai thao tác thừa đó, đây là một lời giải hợp lệ.