Universal Cup Judging System

Universal Cup

時間限制: 10.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

Lucy は Xeppelin コンテストのイラストを準備しています。ある問題のために、彼女はグラフを描くよう頼まれました。しかし、きれいなグラフを描くのは簡単ではありません。

Lucy は、$n$ 個の頂点と $m$ 本の辺を持つ無向連結グラフを描くには方眼紙が最適だと考えています。グラフの各頂点はグリッドの格子点 $(x, y)$ となり、各辺はある整数 $x$ と $y$ に対して点 $(x, y) \leftrightarrow (x + 1, y)$ または $(x, y) \leftrightarrow (x, y + 1)$ を結ぶ線分となります。方眼紙の一部をハイライトするだけでイラストが完成します!

しかし、その描画がグラフ内の距離を保っていればなお良いでしょう。形式的には、$2$ 次元平面上の整数座標を持つ点を考えます。描画とは、そのような $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)$ は平面上の $2$ つの格子点 $p_i$ と $p_j$ の間のマンハッタン距離として定義されます。

与えられたグラフに対するきれいな描画を $1$ つ見つけるか、存在しないことを報告してください。

problem_14142_9546bf960f410fceb2d1e9894a60f686.png

入力

各テストは複数のテストケースを含みます。最初の行にはテストケースの個数 $t$ ($1 \le t \le 50\,000$) が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、グラフの頂点数と辺数を表す $2$ つの整数 $n$ と $m$ ($1 \le n \le 500\,000$, $n - 1 \le m \le 500\,000$) が与えられます。

続く $m$ 行のそれぞれには、グラフの辺で結ばれた $2$ つの頂点を表す $2$ つの整数 $u$ と $v$ ($1 \le u, v \le n$, $u \ne v$) が与えられます。グラフは連結であることが保証されます。

すべてのテストケースにおける $n$ の総和および $m$ の総和はともに $500\,000$ を超えません。

視覚的な見やすさのため、各テストケースの前に空行が $1$ 行入っていますが、無視して構いません。

出力

各テストケースについて、きれいな描画が存在しない場合は $1$ 行に "NO" と出力してください。

そうでない場合は、最初の行に "YES" と出力してください。その後、きれいな描画の例を出力してください。続く $n$ 行のそれぞれには、$i$ 番目の点の座標を表す $2$ つの整数 $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.