Lucy กำลังเตรียมภาพประกอบสำหรับการแข่งขัน Xeppelin สำหรับโจทย์ข้อหนึ่ง เธอได้รับมอบหมายให้วาดกราฟ ปัญหาคือการวาดกราฟให้สวยงามนั้นไม่ใช่เรื่องง่าย
Lucy คิดว่าที่ที่ดีที่สุดในการวาดกราฟไม่มีทิศทางที่เชื่อมต่อกันซึ่งมี $n$ จุดยอดและ $m$ เส้นเชื่อม คือกระดาษตาราง โดยแต่ละจุดยอดของกราฟจะเป็นจุดพิกัดจำนวนเต็มบนตาราง $(x, y)$ และแต่ละเส้นเชื่อมจะเป็นส่วนของเส้นตรงที่เชื่อมระหว่างจุด $(x, y) \leftrightarrow (x + 1, y)$ หรือ $(x, y) \leftrightarrow (x, y + 1)$ สำหรับจำนวนเต็ม $x$ และ $y$ บางค่า เธอเพียงแค่ระบายเน้นบางส่วนของตาราง ภาพประกอบก็จะเสร็จสมบูรณ์!
อย่างไรก็ตาม มันคงจะดีถ้าภาพวาดนั้นรักษาระยะทางในกราฟไว้ได้ด้วย กล่าวอย่างเป็นทางการ ให้พิจารณาจุดที่มีพิกัดเป็นจำนวนเต็มบนระนาบสองมิติ การวาด คืออาเรย์ของจุดดังกล่าวจำนวน $n$ จุด ได้แก่ $p_1, \dots, p_n$ การวาดจะเรียกว่า สวยงาม (nice) หาก $\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