يعد بناء علاقات التطور السلالي بين الكائنات الحية مهمة بالغة الأهمية في المعلوماتية الحيوية.

تُمثَّل علاقات التطور السلالي عادة بشجرة تسمى شجرة التطور السلالي. ويقابل كل كائن حي عقدة ورقية في هذه الشجرة.

يمثل طول المسار بين عقدتين ورقيتين في شجرة التطور السلالي مدى القرابة التطورية بين الكائنين المقابلين لهما.

بالاستعانة بشجرة التطور السلالي، يمكن تعريف رسم بياني يمثل مدى القرابة التطورية بين الكائنات.

يسمى هذا الرسم البياني رسم التطور السلالي.

يُعرَّف رسم التطور السلالي ذي التشابه $K$ كما يأتي.

يمثل كل رأس في الرسم كائنًا حيًا. وتوجد حافة بين رأسين إذا وفقط إذا كانت المسافة (طول المسار) بين العقدتين المقابلتين لهما في شجرة التطور السلالي لا تتجاوز $K$.

أنشأ مختبر رسم تطور سلالي ذا تشابه $3$، ثم فقد بيانات شجرة التطور السلالي. ولذلك يريد إعادة بناء الشجرة.

بإعطائك رسم تطور سلالي ذا تشابه $3$، اكتب برنامجًا يجد شجرة تطور سلالي تُعرِّف هذا الرسم.

لاحظ أن الرسم المدخل متصل دائمًا، وأن وجود شجرة تطور سلالي مقابلة له مضمون.

الإدخال

يحتوي السطر الأول على عدد صحيح $N$ ($2 \le N \le 5000$)، وهو عدد رؤوس رسم التطور السلالي.

الرؤوس مرقمة من $1$ إلى $N$.

يحتوي السطر الثاني على عدد صحيح $M$ ($1 \le M \le 1000000$)، وهو عدد حواف رسم التطور السلالي.

يحتوي كل سطر من الأسطر $M$ التالية على عددين صحيحين $v,w$ ($1 \le v,w \le N$)، وهما رقما طرفي حافة في رسم التطور السلالي.

الإخراج

اطبع في السطر الأول عدد حواف شجرة التطور السلالي $S$.

اطبع في كل سطر من الأسطر $S$ التالية رقمي طرفي حافة، $v$ و$w$، مفصولين بمسافة واحدة.

يمكن طباعة حواف الشجرة بأي ترتيب.

لكن يجب تخصيص أرقام العقد من $1$ إلى $N$ للعقد الورقية.

كما يجب أن يحمل كل رأس في الرسم المدخل والعقدة الورقية المقابلة له في شجرة التطور السلالي الرقم نفسه.

يمكن إسناد الأرقام من $N+1$ إلى $S+1$ إلى العقد الداخلية المتبقية بأي ترتيب. إذا وجدت أكثر من شجرة تطور سلالي واحدة، فأوجد واطبع أي واحدة منها.

أمثلة

الإدخال 1

6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3

الإخراج 1

9
1 7
2 7
3 9
4 8
5 10
6 10
7 9
8 9
9 10

تُمنح 100 نقطة إذا اجتاز الحل جميع الاختبارات، وإلا فتُمنح 0 نقطة.