← 返回题目列表

Codeforces · 1578/C

C. 仙人掌女士和她的 Cing

中文机器翻译题面 查看原题

仙人掌女士非常喜欢她的仙人掌。她特别喜欢一种名叫Cing的小仙人掌。 Cing 可以看作是一个连通的无向图,其中每个顶点至多位于一个简单循环上。直观上,仙人掌是允许存在某些循环的树的概括。不允许使用多重边(一对顶点之间的多条边)和循环(将顶点连接到自身的边)。

她为她特别的小仙人掌Cing买了一个特别的格子。该网格可以表示为由两条长度为 $$$400\,000$$$、$$$u_{(0, -200\,000)} - u_{(0, -199\,999)} - \ldots - u_{(0, 200\,000)}$$$ 和 $$$u_{(1, -200\,000)} - 组成的图。 u_{(1, -199\,999)} - \ldots - u_{(1, 200\,000)}$$$,由 $$$400\,001$$$ 边 $$$(u_{(0, i)}, u_{(1, i)})$$$ 连接在一起,每个 $$$i$$$。换句话说,网格可以看作是梯子。

Cactus lady想知道她是否可以将Cing嵌入到这个网格中,即,将仙人掌的每个顶点映射到网格的单独顶点上,同时将仙人掌的每个边缘映射到网格的某个边缘上。

输入

第一行包含一个整数 $$$t$$$ — 测试用例的数量。

每个测试用例都以包含两个整数 $$$n$$$ 和 $$$m$$$ 的行开始——分别是给定仙人掌的顶点数和边数($$$1 \le n \le 200\,000$$$; $$$0 \le m \le 250\,000$$$)。

以下 $$$m$$$ 行中的每一行都包含两个整数 $$$v$$$ 和 $$$u$$$,描述仙人掌的边缘 ($$$1 \le v, u \le n, u \ne v$$$)。

输入中所有 $$$n$$$ 的总和不超过 $$$200\,000$$$。

输出

按照案例在输入中出现的顺序打印每个测试案例的答案。

对于每个测试用例,如果不存在布局,则在第一行打印“否”。

否则在第一行打印“Yes”,然后在描述布局的 $$$n$$$ 行中打印。这些 $$$n$$$ 行中的第 $$$i$$$ 行应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$,即第 $$$i$$$ 顶点的位置 ($$$0 \le x_i \le 1$$$; $$$-200\,000 \le y_i \le 200\,000$$$)。

示例

输入 #1

5
4 3
1 2
2 3
3 4

8 7
1 2
3 2
2 4
4 5
4 6
6 7
6 8

5 4
1 2
1 3
1 4
1 5

8 9
1 2
2 3
3 4
1 4
4 5
5 6
6 7
7 8
5 8

10 10
1 2
2 3
3 4
4 5
5 6
6 1
3 7
4 8
1 9
6 10

输出 #1

Yes
0 0
0 1
1 1
1 2
Yes
0 3
1 3
1 4
1 2
0 2
1 1
0 1
1 0
No
Yes
0 0
1 0
1 1
0 1
0 2
0 3
1 3
1 2
Yes
1 1
1 2
1 3
0 3
0 2
0 1
1 4
0 4
1 0
0 0

注意

测试用例之间的空行是为了清晰起见。在实际测试用例中没有空行。

在这些注释中,我们考虑测试 2 和 4 的嵌入。

我们从测试 2 的嵌入开始。

这是测试 4 的嵌入。