Ghép đôi công chúa

Một vị vua có $n$ công chúa, đánh số từ $1$ đến $n$. Xung quanh vương quốc có đúng $n$ vương quốc láng giềng, cũng đánh số từ $1$ đến $n$, mỗi vương quốc có một hoàng tử. Công chúa thứ $i$ đưa ra một danh sách các vương quốc mà cô ấy chấp nhận kết hôn với hoàng tử của vương quốc đó.

Nhà vua ghép đôi một cách tham lam, xét lần lượt các công chúa theo thứ tự từ $1$ đến $n$:

• Với công chúa thứ $i$, nhà vua chọn vương quốc có chỉ số nhỏ nhất trong danh sách của cô ấy mà hoàng tử chưa bị ghép đôi, rồi gả công chúa $i$ cho hoàng tử đó.
• Nếu mọi hoàng tử trong danh sách của công chúa $i$ đều đã bị ghép đôi (hoặc danh sách rỗng), công chúa $i$ không kết hôn và nhà vua chuyển sang công chúa tiếp theo.

Trước khi bắt đầu quá trình ghép đôi, nhà vua có thời gian thuyết phục đúng một công chúa bổ sung đúng một vương quốc vào danh sách của cô ấy. Vương quốc được thêm phải chưa có sẵn trong danh sách của công chúa đó. Sau khi thêm, quá trình ghép đôi tham lam ở trên được chạy lại từ đầu.

Hãy xác định xem có cách thêm nào làm tăng tổng số cặp kết hôn hay không. Nếu có, in ra một cách bất kỳ; nếu không, thông báo rằng kết quả đã tối ưu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ là số công chúa và cũng là số vương quốc.
  • $n$ dòng tiếp theo mô tả danh sách của từng công chúa. Dòng thứ $i$ bắt đầu bằng số nguyên $k$ là độ dài danh sách, tiếp theo là $k$ số nguyên phân biệt $g_1,g_2,\dots ,g_k$ theo thứ tự tăng dần, là các chỉ số vương quốc trong danh sách của công chúa $i$.

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Nếu có thể tăng số cặp kết hôn, in ra dòng chứa từ IMPROVE, sau đó một dòng chứa hai số nguyên là chỉ số công chúa và chỉ số vương quốc cần thêm vào danh sách của cô ấy. Nếu có nhiều cách, in ra một cách bất kỳ.
• Ngược lại, in ra một dòng duy nhất chứa từ OPTIMAL.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n\le {10}^5$
• $0\le k\le n$ và $1\le g_1<g_2<\dots <g_k\le n$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$
• Tổng độ dài các danh sách trên tất cả các bộ dữ liệu không vượt quá ${10}^5$

Ví dụ