يواجه بيغي (الذي يدير في أوقات فراغه لجنة بروتوكول الاتصال بين النجوم) معضلةً دقيقةً في العتاد. فشبكة الاتصالات الأحدث، المكوَّنة من $n$ محطات تقوية متصلة بواسطة $(n - 1)$ روابط ألياف بصرية لتشكّل بنية شجرية، أصبحت جاهزةً أخيرًا للنشر. غير أن تشغيل النظام يجب أن يتم بحذر شديد.
تتضمن عملية التفعيل إطلاق نبضات ليزر على طول مسارات محددة. ويُعرَّف المسار بأنه الطريق البسيط الوحيد بين محطتين. وبسبب الخطر الكارثي لظاهرة «تداخل التدفق العكسي الكمومي» — وهي ظاهرة تؤرق محامي اللجنة طوال الليل — يجب الالتزام الصارم بالبروتوكول التالي:
- يجب إنشاء مسارات الإرسال واحدًا تلو الآخر.
- لمنع طفرات الطاقة، يجوز لكل مسار يُنشأ حديثًا أن يشترك في محطة واحدة على الأكثر مع مجموعة المحطات التي تم تفعيلها مسبقًا بواسطة أي مسار سابق.
بصورة رسمية، لتكن $S$ مجموعة المحطات المفعَّلة حاليًا. لأي مسار جديد $P$ يتكون من مجموعة محطات $V(P)$، يجب أن يتحقق الشرط $|V(P) \cap S| \le 1$. وبمجرد إطلاق نبضة بنجاح عبر مسار ما، تُعتبر جميع المحطات الواقعة على طول ذلك المسار جزءًا من المجموعة المفعَّلة $S$.
مهمتك، إن اخترت قبولها، هي تحديد الحد الأدنى لعدد نبضات الليزر اللازمة لتفعيل كل محطة في الشبكة بأكملها وتقديم متتالية واحدة من هذه المسارات لإرضاء القسم القانوني.

رسم توضيحي لحالتي الاختبار الأوليين في المثال. لاحظ أنه في الحالة 2، تشترك النبضة الثانية مع الأولى في المحطة $2$ فقط، مما يحقق قاعدة عدم التداخل.
الإدخال
توجد عدة حالات اختبار. يحتوي السطر الأول من الإدخال على عدد صحيح $T$ ($1 \le T \le 10^4$) يشير إلى عدد حالات الاختبار. ولكل حالة اختبار:
يحتوي السطر الأول على عدد صحيح $n$ ($2 \le n \le 3 \times 10^5$)، وهو عدد المحطات في الشبكة.
وفي الأسطر الـ $(n - 1)$ التالية، يحتوي السطر رقم $i$ على عددين صحيحين $u_i$ و $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)، يصفان رابط ألياف بصرية ثنائي الاتجاه بين المحطة $u_i$ والمحطة $v_i$.
من المضمون أن الروابط تشكّل شجرةً وأن مجموع قيم $n$ عبر جميع حالات الاختبار لا يتجاوز $3 \times 10^5$.
الإخراج
لكل حالة اختبار، اطبع الحد الأدنى لعدد المسارات $k$ في السطر الأول. وبعد ذلك، اطبع $k$ أسطر يحتوي كل منها على عددين صحيحين $a_i$ و $b_i$ يمثلان طرفي المسار رقم $i$ في المتتالية. لاحظ أن $a_i$ قد يساوي $b_i$ إذا كان المسار يتكون من محطة واحدة فقط.
إذا وُجدت عدة متتاليات مثلى، فسيتم قبول أي متتالية تتبع بروتوكول عدم التداخل بدقة.
مثال
الإدخال
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
الإخراج
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5