هذه مسألة تفاعلية.

لدى 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 لعرض تعليمات الاستخدام. تغطي أداة الاختبار فقط بعض سيناريوهات الاختبار والميزات التي يدعمها المتفاعل الرسمي.

أمثلة

الإدخال 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 تلوين الرأس المحاط بدائرة. الأضلاع المتقطعة تم اختيارها مسبقًا.