לוסי מכינה את האיורים לתחרות 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