이 문제는 인터랙티브 문제입니다.

Little Cyan Fish는 $1$부터 $n$까지 번호가 매겨진 $n$개의 정점과 $1$부터 $m$까지 번호가 매겨진 $m$개의 간선으로 이루어진 단순 무방향 그래프를 가지고 있습니다. 처음에 정점 $i$의 색은 $i$입니다.

두 플레이어 A와 B가 $m$개의 라운드로 이루어진 게임을 합니다. 각 라운드에서 두 플레이어는 순서대로 다음 행동을 수행합니다.

• 플레이어 A는 이전의 어떤 라운드에서도 선택되지 않은 간선 $(u, v)$를 하나 선택합니다.
• 플레이어 B는 이 간선의 한 끝점을 선택하고, 그 정점의 색을 다른 끝점의 현재 색으로 변경합니다.

모든 $m$개의 라운드가 끝난 후, 모든 정점의 색이 같으면 플레이어 B가 승리합니다. 그렇지 않으면 플레이어 A가 승리합니다.

Little Cyan Fish는 상대방이 어떻게 행동하든 상관없이 어느 플레이어가 반드시 승리할 수 있는지 당신이 판별하기를 원합니다. 그런 다음 그 플레이어가 되어 그와 대결하여 게임에서 승리하세요.

입력

테스트 케이스가 여러 개 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 하나 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정점의 개수와 간선의 개수를 각각 나타내는 두 정수 $n$과 $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$)이 주어집니다.

다음 $m$개의 줄에는 간선에 대한 정보가 주어집니다. 이 중 $i$번째 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어지며, 이는 간선 $i$가 정점 $u_i$와 $v_i$를 연결함을 의미합니다.

그래프에 자기 루프나 중복 간선이 없음이 보장됩니다. 그래프는 연결 그래프가 아닐 수도 있습니다.

모든 테스트 케이스에 걸쳐 $n$의 합은 $10^5$을 초과하지 않으며, 모든 테스트 케이스에 걸쳐 $m$의 합도 $10^5$을 초과하지 않음이 보장됩니다.

그래프를 하나 읽은 후에는 다음 그래프를 읽기 전에 해당 테스트 케이스에 대한 인터랙션을 완료해야 합니다.

인터랙션

역할을 선택하기 위해 A 또는 B를 포함하는 한 줄을 출력하세요. 플레이어 A가 승리를 보장할 수 있다면 A를 출력하고, 플레이어 B가 승리를 보장할 수 있다면 B를 출력하세요. Little Cyan Fish는 다른 플레이어 역할을 맡습니다.

그런 다음 아래와 같이 정확히 $m$개의 라운드를 진행합니다.

• 당신이 A로 플레이하는 경우, 이전의 어떤 라운드에서도 선택되지 않은 간선의 번호를 나타내는 정수 $e$ ($1 \le e \le m$) 하나를 한 줄에 출력하세요. 그에 대한 응답으로 한 줄에 정수 $x$ 하나가 주어집니다. 정점 $x$는 간선 $e$의 한 끝점이며, 그 색이 다른 끝점의 현재 색으로 변경됩니다.
• 당신이 B로 플레이하는 경우, 이전의 어떤 라운드에서도 선택되지 않은 간선의 번호를 나타내는 정수 $e$ ($1 \le e \le m$) 하나를 한 줄에서 읽으세요. 간선 $e$의 한 끝점을 나타내는 정수 $x$ 하나를 한 줄에 출력하세요. 정점 $x$의 색이 다른 끝점의 현재 색으로 변경됩니다.

모든 $m$개의 라운드가 끝난 후, 정수 하나를 읽으세요. 당신이 올바른 역할을 선택하고 게임에서 승리했다면 이 정수는 1입니다. 1을 받은 후에는 다음 테스트 케이스를 계속 진행하세요. 마지막 테스트 케이스가 끝난 후에는 프로그램을 종료해야 합니다.

잘못된 역할을 선택하거나, 유효하지 않은 수를 두거나, 게임에서 패배하면 인터랙터는 -1을 보냅니다. 어느 시점에라도 -1을 받으면 프로그램은 즉시 종료되어야 합니다.

역할이나 수를 출력한 후에는 줄바꿈 문자를 출력하고 출력 버퍼를 비우는(flush) 것을 잊지 마세요.

테스팅 도구: 참가자들이 풀이를 개발하고 테스트하는 데 도움을 주기 위해 테스팅 도구가 제공됩니다. 이 도구는 첨부 파일에서 다운로드할 수 있습니다. 사용법을 확인하려면 -h 옵션을 사용하여 도구를 실행하세요. 테스팅 도구는 공식 인터랙터가 지원하는 테스트 시나리오와 기능 중 일부만 다룹니다.

예제

입력 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

출력 1

B

3

1






A
1

3

2

참고

예제의 두 게임이 아래에 나타나 있습니다. 각 단계에서 A는 강조 표시된 간선을 선택하고, B는 동그라미가 쳐진 정점의 색을 다시 칠합니다. 점선으로 표시된 간선은 이전에 선택된 간선입니다.