Universal Cup Judging System

Universal Cup

Time Limit: 10.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Lucy는 Xeppelin 대회의 삽화를 준비하고 있습니다. 한 문제를 위해 그녀는 그래프를 그려달라는 요청을 받았습니다. 문제는 멋진 그래프를 그리기가 쉽지 않다는 점입니다.

Lucy는 $n$개의 정점과 $m$개의 간선을 가진 무방향 연결 그래프를 그리기에 가장 좋은 곳이 모눈종이라고 생각합니다. 그래프의 각 정점은 격자의 정수 점 $(x, y)$가 되고, 각 간선은 어떤 정수 $x$와 $y$에 대해 점 $(x, y) \leftrightarrow (x + 1, y)$ 또는 $(x, y) \leftrightarrow (x, y + 1)$을 잇는 선분이 됩니다. 모눈 패턴의 일부를 강조 표시하기만 하면 삽화가 완성됩니다!

하지만 그림이 그래프에서의 거리를 보존한다면 더욱 좋을 것입니다. 공식적으로, 2차원 평면에서 정수 좌표를 가지는 점들을 생각해 봅시다. 그림(drawing)이란 이러한 $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$ 사이의 맨해튼 거리로 정의됩니다.

주어진 그래프에 대해 멋진 그림을 찾거나, 존재하지 않음을 판별하십시오.

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

입력

각 테스트는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 개수 $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$개의 줄에는 각각 $i$번째 점의 좌표를 나타내는 두 정수 $x_i$와 $y_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

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.