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