זוהי בעיה אינטראקטיבית.

ל-Little Cyan Fish יש גרף פשוט לא מכוון עם $n$ צמתים המסומנים מ-$1$ עד $n$ ו-$m$ קשתות המסומנות מ-$1$ עד $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$) בשורה, האינדקס של קשת שלא נבחרה באף סיבוב קודם. הדפיסו שורה המכילה מספר שלם יחיד $x$, קצה של הקשת $e$. הצבע של צומת $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 צובע מחדש את הצומת המוקף בעיגול. קשתות מקווקוות נבחרו מוקדם יותר.