Бұл — интерактивті есеп.

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 опциясымен іске қосыңыз. Тестілеу құралы ресми интерактор қолдайтын тестілеу сценарийлері мен мүмкіндіктерінің бір бөлігін ғана қамтиды.

Examples

Input 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Output 1

B

3

1






A
1

3

2

Note

Мысалдағы екі ойын төменде көрсетілген. Әр қадамда A ерекшеленген қабырғаны таңдайды, ал B қоршалған төбені қайта бояйды. Үзік сызықты қабырғалар ертерек таңдалған.