Bộ ghép cặp hay tập độc lập

Cho một đồ thị vô hướng đơn (không có khuyên, không có cạnh kép) với $3n$ đỉnh và $m$ cạnh. Các đỉnh được đánh số từ $1$ đến $3n$, các cạnh được đánh số từ $1$ đến $m$ theo thứ tự xuất hiện trong dữ liệu vào.

Bạn cần tìm một trong hai cấu trúc sau:

• Một bộ ghép cặp (matching) gồm đúng $n$ cạnh — tập các cạnh sao cho không có hai cạnh nào dùng chung một đỉnh.
• Một tập độc lập (independent set) gồm đúng $n$ đỉnh — tập các đỉnh sao cho không có hai đỉnh nào được nối với nhau bởi một cạnh.

Nếu cả hai cấu trúc đều không tồn tại, hãy thông báo điều đó (tuy nhiên, có thể chứng minh rằng với mọi đồ thị thoả mãn ràng buộc, ít nhất một trong hai cấu trúc luôn tồn tại). Nếu tồn tại cả bộ ghép cặp lẫn tập độc lập kích thước $n$, in ra một trong hai cũng được; nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Dữ liệu vào chứa $T$ đồ thị độc lập, hãy xử lý từng đồ thị.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$ — số đồ thị cần xử lý ($T\ge 1$).
• Với mỗi đồ thị:
  • Dòng đầu chứa hai số nguyên $n$ và $m$ ($1\le n\le {10}^5$, $0\le m\le 5·{10}^5$).
  • $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ ($1\le u_i,v_i\le 3n$, $u_i\ne v_i$) mô tả một cạnh nối $u_i$ với $v_i$.

Tổng $n$ trên tất cả đồ thị không vượt quá ${10}^5$, tổng $m$ không vượt quá $5·{10}^5$.

Dữ liệu ra

Với mỗi đồ thị, in ra kết quả theo định dạng:

• Nếu chọn bộ ghép cặp: dòng đầu in Matching, dòng thứ hai in $n$ số nguyên — chỉ số các cạnh thuộc bộ ghép cặp.
• Nếu chọn tập độc lập: dòng đầu in IndSet, dòng thứ hai in $n$ số nguyên — chỉ số các đỉnh thuộc tập độc lập.
• Nếu cả hai đều không tồn tại: in Impossible.

Các chỉ số có thể in theo thứ tự bất kỳ.

Ví dụ