Đường kính của cây

Đây là bài toán tương tác.

Hệ thống giữ bí mật một cây có trọng số gồm $n$ đỉnh được đánh số từ $1$ đến $n$ và $n-1$ cạnh. Mỗi cạnh có trọng số là một số nguyên dương không vượt quá $100$. Khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi duy nhất nối chúng.

Nhiệm vụ của bạn là tìm đường kính của cây — tức khoảng cách lớn nhất giữa một cặp đỉnh bất kỳ.

Bạn không được cho biết cây, nhưng có thể đặt câu hỏi. Mỗi câu hỏi gồm hai tập đỉnh khác rỗng và rời nhau $p$ và $q$; hệ thống trả về khoảng cách lớn nhất giữa một đỉnh thuộc $p$ và một đỉnh thuộc $q$, tức ${max}_{x\in p,y\in q}\text{dist}(x,y)$. Bạn được hỏi không quá $9$ câu hỏi cho mỗi cây.

Dữ liệu vào

Đầu tiên hệ thống in ra một dòng chứa số nguyên $t$ — số lượng bộ dữ liệu. Sau đó là $t$ bộ dữ liệu. Với mỗi bộ, hệ thống in ra một dòng chứa số nguyên $n$ — số đỉnh của cây hiện tại.

Giao thức tương tác

Với mỗi cây, sau khi đọc $n$ bạn thực hiện:

• Để hỏi, in ra một dòng k_1 k_2 a_1 a_2 ... a_{k_1} b_1 b_2 ... b_{k_2}, trong đó $k_1,k_2\ge 1$ và $k_1+k_2\le n$. Đây là tập $p=\{a_1,\dots ,a_{k_1}\}$ và tập $q=\{b_1,\dots ,b_{k_2}\}$; hai tập phải rời nhau. Hệ thống trả lời bằng một số nguyên là khoảng cách lớn nhất giữa hai tập.
• Khi đã biết đáp án, in ra một dòng -1 d, trong đó $d$ là đường kính của cây, rồi chuyển sang cây tiếp theo (hoặc kết thúc nếu đây là cây cuối). Dòng này không tính là một câu hỏi.

Nếu bạn hỏi quá $9$ câu hỏi cho một cây, đặt câu hỏi không hợp lệ, hoặc đưa ra đáp án sai, bạn sẽ nhận kết quả sai.

Quan trọng: Sau mỗi lần in ra, bạn phải flush output:

• C++: cout << endl; hoặc cout.flush();
• Python: print(..., flush=True)

Ràng buộc

• $1\le t\le 1000$
• $2\le n\le 100$
• Trọng số mỗi cạnh là số nguyên trong đoạn $[1,100]$.

Ví dụ