Lucy sedang menyiapkan ilustrasi untuk Kontes Xeppelin. Untuk salah satu soal, ia diminta menggambar sebuah graf. Masalahnya, tidak mudah untuk menggambar graf yang bagus.
Lucy berpikir bahwa tempat terbaik untuk menggambar graf terhubung tak berarah dengan $n$ simpul dan $m$ sisi adalah kertas berpetak. Setiap simpul dari graf akan menjadi titik bulat pada kisi $(x, y)$, dan setiap sisi akan menjadi garis yang menghubungkan titik $(x, y) \leftrightarrow (x + 1, y)$ atau $(x, y) \leftrightarrow (x, y + 1)$ untuk suatu bilangan bulat $x$ dan $y$. Ia cukup menyorot beberapa bagian dari pola berpetak tersebut, dan ilustrasinya akan siap!
Namun, akan lebih baik jika gambar tersebut mempertahankan jarak di dalam graf. Secara formal, tinjau titik-titik dengan koordinat bulat pada bidang dua dimensi. Sebuah gambar adalah sebuah larik yang terdiri atas $n$ titik demikian $p_1, \dots, p_n$. Sebuah gambar dikatakan bagus jika $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ untuk semua $i$ dan $j$ yang mungkin. Di sini, $\operatorname{dist}(u, v)$ didefinisikan sebagai banyaknya sisi pada lintasan terpendek antara simpul $u$ dan $v$ di dalam graf, sedangkan $\operatorname{Manhattan}(p_i, p_j)$ didefinisikan sebagai jarak Manhattan antara dua titik bulat $p_i$ dan $p_j$ pada bidang.
Temukan sebuah gambar yang bagus untuk graf yang diberikan atau nyatakan bahwa gambar demikian tidak ada.
Masukan
Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi banyaknya kasus uji $t$ ($1 \le t \le 50\,000$). Deskripsi dari masing-masing kasus uji menyusul.
Baris pertama dari setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): banyaknya simpul dan sisi di dalam graf.
Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$): dua simpul yang dihubungkan oleh sebuah sisi pada graf. Graf dijamin terhubung.
Baik jumlah nilai $n$ maupun jumlah nilai $m$ di seluruh kasus uji tidak melebihi $500\,000$.
Untuk kenyamanan visual, terdapat satu baris kosong sebelum setiap kasus uji. Baris kosong ini dapat diabaikan.
Keluaran
Untuk setiap kasus uji, cetak "NO" pada satu baris jika tidak ada gambar yang bagus.
Sebaliknya, cetak "YES" pada baris pertama. Setelah itu, cetak sebuah contoh gambar yang bagus. Masing-masing dari $n$ baris berikutnya harus berisi dua bilangan bulat $x_i$ dan $y_i$: koordinat dari titik ke-$i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Jika terdapat beberapa kemungkinan jawaban, cetak salah satu di antaranya.
Contoh
Contoh Masukan 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
Contoh Keluaran 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
Contoh Masukan 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
Contoh Keluaran 2
NO NO