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

Little Cyan Fish có một đồ thị vô hướng đơn gồm $n$ đỉnh được đánh số từ $1$ đến $n$ và $m$ cạnh được đánh số từ $1$ đến $m$. Ban đầu, màu của đỉnh $i$ là $i$.

Hai người chơi, A và B, chơi một trò chơi gồm $m$ vòng. Trong mỗi vòng, hai người chơi lần lượt thực hiện các hành động sau theo thứ tự:

• Người chơi A chọn một cạnh $(u, v)$ chưa từng được chọn ở bất kỳ vòng nào trước đó.
• Người chơi B chọn một đầu mút của cạnh này và đổi màu của nó thành màu hiện tại của đầu mút còn lại.

Sau tất cả $m$ vòng, Người chơi B thắng nếu tất cả các đỉnh đều có cùng một màu. Ngược lại, Người chơi A thắng.

Little Cyan Fish muốn bạn xác định xem người chơi nào có thể đảm bảo chiến thắng bất kể các nước đi của người chơi kia. Sau đó hãy đóng vai người chơi đó đấu với cậu ấy và giành chiến thắng.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), lần lượt cho biết số lượng đỉnh và số lượng cạnh.

$m$ dòng tiếp theo mô tả các cạnh. Dòng thứ $i$ trong các dòng này chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), có nghĩa là cạnh $i$ nối hai đỉnh $u_i$ và $v_i$.

Dữ liệu đảm bảo đồ thị không có khuyên hay đa cạnh. Đồ thị có thể không liên thông.

Dữ liệu đảm bảo tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $10^5$, và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Sau khi đọc xong một đồ thị, hãy hoàn thành phần giao tiếp của bộ dữ liệu đó trước khi đọc đồ thị tiếp theo.

Giao tiếp

Để chọn vai của bạn, hãy in ra một dòng chứa A hoặc B. In ra A nếu Người chơi A có thể đảm bảo chiến thắng, hoặc B nếu Người chơi B có thể đảm bảo chiến thắng. Little Cyan Fish sẽ đóng vai người chơi còn lại.

Sau đó hãy chơi đúng $m$ vòng như sau.

• Nếu bạn đóng vai A, hãy in ra một dòng chứa một số nguyên $e$ ($1 \le e \le m$), là chỉ số của một cạnh chưa từng được chọn ở bất kỳ vòng nào trước đó. Để phản hồi, bạn sẽ nhận được một số nguyên $x$ trên một dòng. Đỉnh $x$ là một đầu mút của cạnh $e$, và màu của nó được đổi thành màu hiện tại của đầu mút còn lại.
• Nếu bạn đóng vai B, hãy đọc một số nguyên $e$ ($1 \le e \le m$) trên một dòng, là chỉ số của một cạnh chưa từng được chọn ở bất kỳ vòng nào trước đó. Hãy in ra một dòng chứa một số nguyên $x$, là một đầu mút của cạnh $e$. Màu của đỉnh $x$ sẽ được đổi thành màu hiện tại của đầu mút còn lại.

Sau tất cả $m$ vòng, hãy đọc một số nguyên. Số nguyên này là 1 nếu bạn đã chọn đúng vai và thắng trò chơi. Sau khi nhận được 1, hãy tiếp tục với bộ dữ liệu tiếp theo. Sau bộ dữ liệu cuối cùng, chương trình của bạn phải kết thúc.

Trình chấm tương tác sẽ gửi -1 nếu bạn chọn sai vai, thực hiện nước đi không hợp lệ, hoặc thua trò chơi. Nếu bạn nhận được -1 ở bất kỳ thời điểm nào, chương trình của bạn phải kết thúc ngay lập tức.

Sau khi in ra vai hoặc nước đi của bạn, đừng quên in ký tự xuống dòng và làm rỗng bộ đệm đầu ra (flush).

Công cụ kiểm thử: Một công cụ kiểm thử được cung cấp để giúp thí sinh phát triển và kiểm thử lời giải của mình. Bạn có thể tải công cụ này từ phần tệp đính kèm. Chạy công cụ với tùy chọn -h để hiển thị hướng dẫn sử dụng. Công cụ kiểm thử chỉ bao gồm một số kịch bản kiểm thử và tính năng được hỗ trợ bởi trình chấm tương tác chính thức.

Ví dụ

Dữ liệu vào 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Dữ liệu ra 1

B

3

1






A
1

3

2

Ghi chú

Hai ván chơi trong ví dụ được minh họa dưới đây. Ở mỗi bước, A chọn cạnh được tô đậm và B tô lại màu cho đỉnh được khoanh tròn. Các cạnh nét đứt đã được chọn ở các bước trước đó.