Lucy przygotowuje ilustracje na zawody Xeppelin Contest. W jednym z zadań poproszono ją o narysowanie grafu. Problem polega na tym, że niełatwo jest narysować ładny graf.
Lucy uważa, że najlepszym miejscem do narysowania nieskierowanego grafu spójnego o $n$ wierzchołkach i $m$ krawędziach jest papier w kratkę. Każdy wierzchołek grafu będzie punktem kratowym o współrzędnych całkowitych $(x, y)$, a każda krawędź będzie odcinkiem łączącym punkty $(x, y) \leftrightarrow (x + 1, y)$ lub $(x, y) \leftrightarrow (x, y + 1)$ dla pewnych liczb całkowitych $x$ i $y$. Wystarczy zaznaczyć niektóre fragmenty kratki i ilustracja będzie gotowa!
Byłoby jednak dobrze, gdyby rysunek zachowywał odległości w grafie. Formalnie, rozważmy punkty o współrzędnych całkowitych na płaszczyźnie dwuwymiarowej. Rysunkiem nazywamy tablicę $n$ takich punktów $p_1, \dots, p_n$. Rysunek jest ładny, jeśli $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ dla wszystkich możliwych $i$ oraz $j$. Tutaj $\operatorname{dist}(u, v)$ oznacza liczbę krawędzi na najkrótszej ścieżce między wierzchołkami $u$ i $v$ w grafie, natomiast $\operatorname{Manhattan}(p_i, p_j)$ oznacza odległość manhattańską między dwoma punktami całkowitymi $p_i$ oraz $p_j$ na płaszczyźnie.
Znajdź ładny rysunek dla danego grafu lub wskaż, że taki nie istnieje.
Wejście
Każdy test zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę przypadków testowych $t$ ($1 \le t \le 50\,000$). Poniżej znajduje się opis przypadków testowych.
Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): liczbę wierzchołków i krawędzi w grafie.
Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$, $u \ne v$): dwa wierzchołki połączone krawędzią grafu. Graf jest spójny.
Zarówno suma $n$, jak i suma $m$ po wszystkich przypadkach testowych nie przekraczają $500\,000$.
Dla wygody wizualnej przed każdym przypadkiem testowym znajduje się pusty wiersz. Można go zignorować.
Wyjście
Dla każdego przypadku testowego wypisz w pojedynczym wierszu "NO", jeśli ładny rysunek nie istnieje.
W przeciwnym razie wypisz w pierwszym wierszu "YES". Następnie wypisz przykład ładnego rysunku. Każdy z kolejnych $n$ wierszy powinien zawierać dwie liczby całkowite $x_i$ oraz $y_i$: współrzędne $i$-tego punktu ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Jeśli istnieje wiele możliwych odpowiedzi, wypisz dowolną z nich.
Przykłady
Przykładowe wejście 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
Przykładowe wyjście 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
Przykładowe wejście 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
Przykładowe wyjście 2
NO NO