Lucy đang chuẩn bị các hình minh họa cho kỳ thi Xeppelin. Đối với một trong các bài toán, cô được yêu cầu vẽ một đồ thị. Vấn đề là việc vẽ được một đồ thị đẹp không hề dễ dàng.
Lucy nghĩ rằng nơi tốt nhất để vẽ một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh là giấy kẻ ô vuông. Mỗi đỉnh của đồ thị sẽ là một điểm nguyên trên lưới $(x, y)$, và mỗi cạnh sẽ là một đoạn thẳng nối hai điểm $(x, y) \leftrightarrow (x + 1, y)$ hoặc $(x, y) \leftrightarrow (x, y + 1)$ với các số nguyên $x$ và $y$ nào đó. Cô chỉ cần tô đậm một số phần của mẫu kẻ ô vuông là hình minh họa sẽ hoàn tất!
Tuy nhiên, sẽ thật tuyệt nếu hình vẽ bảo toàn được khoảng cách trong đồ thị. Một cách hình thức, xét các điểm có tọa độ nguyên trên mặt phẳng hai chiều. Một hình vẽ là một mảng gồm $n$ điểm như vậy $p_1, \dots, p_n$. Một hình vẽ được gọi là đẹp nếu $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ với mọi cặp $i$ và $j$ có thể. Ở đây, $\operatorname{dist}(u, v)$ được định nghĩa là số cạnh trên đường đi ngắn nhất giữa hai đỉnh $u$ và $v$ trong đồ thị, còn $\operatorname{Manhattan}(p_i, p_j)$ được định nghĩa là khoảng cách Manhattan giữa hai điểm nguyên $p_i$ và $p_j$ trên mặt phẳng.
Hãy tìm một hình vẽ đẹp cho đồ thị đã cho hoặc chỉ ra rằng nó không tồn tại.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 50\,000$). Mô tả của các bộ dữ liệu tiếp theo như sau.
Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): số lượng đỉnh và cạnh trong đồ thị.
Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$): hai đỉnh được nối với nhau bởi một cạnh của đồ thị. Đồ thị đảm bảo liên thông.
Cả tổng của $n$ và tổng của $m$ trong tất cả các bộ dữ liệu đều không vượt quá $500\,000$.
Để thuận tiện cho việc quan sát, có một dòng trống trước mỗi bộ dữ liệu. Bạn có thể bỏ qua dòng này.
Kết quả
Với mỗi bộ dữ liệu, in ra "NO" trên một dòng nếu không tồn tại hình vẽ đẹp.
Ngược lại, in ra "YES" ở dòng đầu tiên. Sau đó, in ra một ví dụ về hình vẽ đẹp. Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $x_i$ và $y_i$: tọa độ của điểm thứ $i$ ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). Nếu có nhiều đáp án thỏa mãn, hãy in ra bất kỳ đáp án nào.
Ví dụ
Dữ liệu vào 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
Kết quả 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
Dữ liệu vào 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
Kết quả 2
NO NO