Bảo đang có một đồ thị vô hướng cần được xử lý. Mục tiêu của Bảo là biến đồ thị trên thành một cây$$$^\dagger$$$ duy nhất.
Vì quá bận Bảo quyết định nhờ bạn giúp xử lí đồ thị trên. Bạn được phép thực hiện các thao tác sau:
- Xóa cạnh: Loại bỏ một cạnh bất kỳ khỏi đồ thị.
- Thêm cạnh: Thêm một cạnh vô hướng mới giữa hai đỉnh bất kỳ.
Cây$$$^\dagger$$$: Là một đồ thị đơn giản (simple graph), vô hướng, không chu trình và liên thông.
Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 1000$$$) $$$-$$$ số testcases.
Dòng đầu tiên của mỗi testcase gồm hai số nguyên $$$n$$$ và $$$m$$$ ($$$0 \le m \le 5 \cdot 10^5$$$, $$$1 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số đỉnh và cạnh của đồ thị.
$$$m$$$ dòng tiếp theo của mỗi testcase gồm hai số nguyên dương $$$u_i$$$ và $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) $$$-$$$ biểu diễn cạnh thứ $$$i$$$ ($$$1 \le i \le m$$$) của đồ thị.
Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$ và tổng $$$m$$$ ở mọi testcases không vượt quá $$$5 \cdot 10^5$$$.
Với mỗi testcase in ra như sau:
Dòng đầu tiên là một số nguyên $$$k$$$ thể hiện số cạnh bị xóa.
$$$k$$$ dòng tiếp theo in ra một số nguyên dương $$$i$$$ ($$$1 \le i \le m$$$) $$$-$$$ cạnh được chọn để xóa.
Dòng thứ tiếp theo in ra một số nguyên dương $$$t$$$ thể hiện số cạnh được thêm.
$$$t$$$ dòng tiếp theo in ra hai số nguyên dương $$$u$$$ và $$$v$$$ ($$$1 \le u, v \le n$$$) $$$-$$$ biểu diễn cạnh thêm.
15 61 11 22 31 34 55 4
3 1 4 6 1 1 4
Tại ví dụ thứ nhất, các thao tác có thể được biểu diễn như sau:
Đồ thị ban đầu. 
Đồ thị sau khi xóa cạnh. 
Đồ thị sau khi thêm cạnh.
