Universal Cup Judging System

Universal Cup

Süre Sınırı: 10.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Lucy is preparing the illustrations for Xeppelin Contest. For one of the problems, she was asked to draw a graph. The issue is, it is not easy to draw a nice graph.

Lucy thinks that the best place to draw an undirected connected graph with $n$ vertices and $m$ edges is checkered paper. Each vertex of the graph will be an integer point of the grid $(x, y)$, and each edge will be a line connecting either points $(x, y) \leftrightarrow (x + 1, y)$ or $(x, y) \leftrightarrow (x, y + 1)$ for some integers $x$ and $y$. She can just highlight some parts of the checkered pattern, and the illustration will be ready!

However, it would be nice if the drawing preserved the distances in the graph. Formally, consider points with integer coordinates on a two-dimensional plane. A drawing is an array of $n$ such points $p_1, \dots, p_n$. A drawing is nice if $\operatorname{dist}(i, j) = \operatorname{Manhattan}(p_i, p_j)$ for all possible $i$ and $j$. Here, $\operatorname{dist}(u, v)$ is defined as the number of edges on the shortest path between vertices $u$ and $v$ in the graph, while $\operatorname{Manhattan}(p_i, p_j)$ is defined as the Manhattan distance between two integer points $p_i$ and $p_j$ on the plane.

Find a nice drawing for the given graph or indicate that it does not exist.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$): the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$): the two vertices connected by an edge of the graph. The graph is connected.

Both the sum of $n$ and the sum of $m$ over all test cases don't exceed $500\,000$.

For the convenience of visual perception, there is an empty line before every test case. It can be ignored.

Output

For each test case, print "NO" on a single line if no nice drawing exists.

Otherwise, print "YES" on the first line. After that, print an example of a nice drawing. Each of the following $n$ lines should contain two integers $x_i$ and $y_i$: the coordinates of the $i$-th point ($-998\,244\,353 \le x_i, y_i \le 998\,244\,353$). If there are several possible answers, print any one of them.

Examples

Sample Input 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

Sample Output 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

Sample Input 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

Sample Output 2

NO
NO

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.