Це інтерактивна задача.

У Маленької Ціанової Рибки (Little Cyan Fish) є простий неорієнтований граф із $n$ вершинами, пронумерованими від $1$ до $n$, та $m$ ребрами, пронумерованими від $1$ до $m$. Початково колір вершини $i$ дорівнює $i$.

Два гравці, A і B, грають у гру, що складається з $m$ раундів. У кожному раунді гравці по черзі виконують такі дії:

• Гравець A обирає ребро $(u, v)$, яке не обиралося в жодному з попередніх раундів.
• Гравець B обирає один із кінців цього ребра і змінює його колір на поточний колір іншого кінця.

Після всіх $m$ раундів гравець B перемагає, якщо всі вершини мають однаковий колір. Інакше перемагає гравець A.

Маленька Ціанова Рибка хоче, щоб ви визначили, який гравець може гарантувати собі перемогу незалежно від ходів іншого гравця. Потім зіграйте за цього гравця проти нього та виграйте гру.

Вхідні дані

Є декілька наборів вхідних даних. Перший рядок вхідних даних містить одне ціле число $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 може гарантувати собі перемогу. Маленька Ціанова Рибка гратиме за іншого гравця.

Потім зіграйте рівно $m$ раундів таким чином.

• Якщо ви граєте за A, виведіть рядок, що містить одне ціле число $e$ ($1 \le e \le m$) — номер ребра, яке не обиралося в жодному з попередніх раундів. У відповідь ви отримаєте одне ціле число $x$ в окремому рядку. Вершина $x$ є кінцем ребра $e$, і її колір змінюється на поточний колір іншого кінця.
• Якщо ви граєте за B, зчитайте одне ціле число $e$ ($1 \le e \le m$) в окремому рядку — номер ребра, яке не обиралося в жодному з попередніх раундів. Виведіть рядок, що містить одне ціле число $x$ — кінець ребра $e$. Колір вершини $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 перефарбовує обведену кружечком вершину. Пунктирні ребра були обрані раніше.