تقوم لوسي بإعداد الرسوم التوضيحية لمسابقة Xeppelin. في إحدى المسائل، طُلب منها رسم بيان. المشكلة هي أنه ليس من السهل رسم بيان جميل.
تعتقد لوسي أن أفضل مكان لرسم بيان متصل غير موجه يحتوي على $n$ من الرؤوس و $m$ من الحواف هو الورق المربع (المخطط). سيكون كل رأس في البيان نقطة ذات إحداثيات صحيحة على الشبكة $(x, y)$، وستكون كل حافة قطعة مستقيمة تصل إما بين النقطتين $(x, y) \leftrightarrow (x + 1, y)$ أو $(x, y) \leftrightarrow (x, y + 1)$ لبعض الأعداد الصحيحة $x$ و $y$. يمكنها فقط تظليل بعض أجزاء نمط المربعات، وسيكون الرسم التوضيحي جاهزاً!
ومع ذلك، سيكون من الجميل لو حافظ الرسم على المسافات في البيان. رسمياً، لنأخذ بعين الاعتبار النقاط ذات الإحداثيات الصحيحة في مستوٍ ثنائي الأبعاد. الرسم هو مصفوفة مكونة من $n$ من هذه النقاط $p_1, \dots, p_n$. يُقال عن الرسم إنه جميل إذا كان $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ لجميع قيم $i$ و $j$ الممكنة. هنا، يُعرَّف $\operatorname{dist}(u, v)$ بأنه عدد الحواف في أقصر مسار بين الرأسين $u$ و $v$ في البيان، بينما يُعرَّف $\operatorname{Manhattan}(p_i, p_j)$ بأنه مسافة مانهاتن بين نقطتين صحيحتين $p_i$ و $p_j$ في المستوي.
أوجد رسماً جميلاً للبيان المعطى أو أشر إلى أنه غير موجود.
الإدخال
يحتوي كل اختبار على عدة حالات اختبار. يحتوي السطر الأول على عدد حالات الاختبار $t$ ($1 \le t \le 50\,000$). يلي ذلك وصف حالات الاختبار.
يحتوي السطر الأول من كل حالة اختبار على عددين صحيحين $n$ و $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): عدد الرؤوس والحواف في البيان.
يحتوي كل سطر من الأسطر الـ $m$ التالية على عددين صحيحين $u$ و $v$ ($1 \le u, v \le n$, $u \ne v$): الرأسان المتصلان بحافة من البيان. البيان متصل.
لا يتجاوز كل من مجموع $n$ ومجموع $m$ عبر جميع حالات الاختبار $500\,000$.
لتسهيل الإدراك البصري، يوجد سطر فارغ قبل كل حالة اختبار. يمكن تجاهله.
الإخراج
لكل حالة اختبار، اطبع "NO" في سطر منفرد إذا لم يكن هناك رسم جميل.
وإلا، اطبع "YES" في السطر الأول. بعد ذلك، اطبع مثالاً على رسم جميل. يجب أن يحتوي كل سطر من الأسطر الـ $n$ التالية على عددين صحيحين $x_i$ و $y_i$: إحداثيات النقطة الـ $i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). إذا كانت هناك عدة إجابات ممكنة، فاطبع أياً منها.
أمثلة
إدخال المثال 1
3 4 4 1 2 2 3 3 4 4 1 5 4 1 2 1 3 1 4 1 5 7 8 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7
إخراج المثال 1
YES 0 0 1 0 1 1 0 1 YES 3 1 2 1 3 0 4 1 3 2 YES 1 2 2 2 1 3 2 3 3 3 2 4 3 4
إدخال المثال 2
2 6 6 1 2 2 3 3 4 4 5 5 6 6 1 12 16 1 2 1 3 2 4 3 4 3 5 4 6 5 6 6 7 4 8 7 8 7 9 8 10 9 10 8 11 10 12 11 12
إخراج المثال 2
NO NO