Cover it! (Phủ đồ thị)

Cho một đồ thị vô hướng, liên thông, không trọng số gồm $n$ đỉnh và $m$ cạnh. Đồ thị không có khuyên (cạnh nối một đỉnh với chính nó) và không có cạnh bội.

Nhiệm vụ của bạn là chọn ra không quá $\lfloor n/2\rfloor$ đỉnh sao cho mỗi đỉnh không được chọn đều kề (nối trực tiếp bằng một cạnh) với ít nhất một đỉnh đã chọn.

Đề bài đảm bảo luôn tồn tại đáp án. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án hợp lệ nào.

Có nhiều truy vấn độc lập cần trả lời.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng truy vấn.
• Với mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh và số cạnh.
  • $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $v_i,u_i$ — hai đỉnh được nối bởi cạnh thứ $i$.

Đề bài đảm bảo mỗi đồ thị đều liên thông, không khuyên và không cạnh bội.

Dữ liệu ra

Với mỗi truy vấn, in ra hai dòng:

• Dòng đầu chứa số $k$ ($1\le k\le \lfloor n/2\rfloor$) — số đỉnh được chọn.
• Dòng thứ hai chứa $k$ số nguyên phân biệt — chỉ số các đỉnh được chọn, theo thứ tự bất kỳ.

Ràng buộc

• $1\le t\le 2·{10}^5$
• $2\le n\le 2·{10}^5$
• $n-1\le m\le min(2·{10}^5,{\displaystyle \frac{n(n-1)}{2}})$
• $1\le v_i,u_i\le n$, $u_i\ne v_i$
• Tổng $m$ trên tất cả các truy vấn không vượt quá $2·{10}^5$.

Ví dụ