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$。如果對於所有可能的 $i$ 和 $j$,都有 $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$,則稱該繪製方案是美妙的(nice)。這裡,$\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