Cactus Lady and her 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)} $ , 通过 $ 400001 $ 条边连接在一起：对每个 $ i $ ， $ (u_{(0, i)}, u_{(1, i)}) $ .换句话说，网格可以被视为"梯子"。  仙人掌女士想知道她是否可以将Cing嵌入到这个网格中，即将仙人掌的每个顶点映射到网格的一个单独的顶点上，而仙人掌每个边将映射到网格中的某个边上。 ## 输入格式 第一行包含一个整数 $ t $ —— 测试用例的数量。 每个测试用例的第一行，包含两个整数 $n$ 和 $m$ —— 分别是给定仙人掌中的顶点数和边数（$1\le n\le 200000$；$0\le m\le 250000$）。 以下 $ m $ 行，每行包含两个整数 $v$ 和 $u$ ，用于描述仙人掌的边缘（$ 1\le v，u\le n，u\ne v $）。 输入中所有 $n$ 的总和不超过 $200000$ 。 ## 输出格式 按照样例输入出现的相同顺序打印每个测试案例的答案。 对于每个测试用例，如果没有合法解，则在第一行打印“No”。 否则，在第一行打印“Yes”，并在下面的 $ n $ 行中描述点的坐标. $ n $ 行中的 第 $ i $ 行 是两个整数 $ x_i $ and $ y_i $ , 第 $ i $ 个点的位置坐标 ( $ 0 \le x_i \le 1 $ ; $ -200\,000 \le y_i \le 200\,000 $ ). ## 样例 #1 ### 样例输入 #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的解释。 

题目描述

Cactus lady loves her cactuses very much. Especially she likes a small cactus named Cing. Cing can be seen as a connected undirected graph in which every vertex lies on at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed. She bought a special grid for her special little cactus Cing. This grid can be represented as a graph consisting of two paths of length $ 400\,000 $ , $ u_{(0, -200\,000)} - u_{(0, -199\,999)} - \ldots - u_{(0, 200\,000)} $ and $ u_{(1, -200\,000)} - u_{(1, -199\,999)} - \ldots - u_{(1, 200\,000)} $ , connected together by $ 400\,001 $ edges $ (u_{(0, i)}, u_{(1, i)}) $ for each $ i $ . In other words, a grid can be seen as a ladder. Cactus lady wants to know whether she can embed Cing into this grid, i.e., map each vertex of the cactus onto a separate vertex of the grid while each edge of the cactus will be mapped onto some edge of the grid.

输入输出格式

输入格式

The first line contains an integer $ t $ — the number of test cases. Each test case begins with a line containing two integers $ n $ and $ m $ — the number of vertices and the number of edges in a given cactus, respectively ( $ 1 \le n \le 200\,000 $ ; $ 0 \le m \le 250\,000 $ ). Each of the following $ m $ lines contains two integers $ v $ and $ u $ , describing the edges of the cactus ( $ 1 \le v, u \le n, u \ne v $ ). The total sum of all $ n $ in the input doesn't exceed $ 200\,000 $ .

输出格式

Print an answer for each test case in the same order the cases appear in the input. For each test case print "No" in the first line, if no layout exists. Otherwise print "Yes" in the first line, and the following $ n $ lines describing the layout. The $ i $ -th of these $ n $ lines should contain two integers $ x_i $ and $ y_i $ , the location of the $ i $ -th vertex ( $ 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

说明

Empty lines between test cases are for clarity. In real test cases there are no empty lines. In these notes, we consider the embeddings for tests 2 and 4. We start with the embedding for test 2. Here goes the embedding for test 4. 

题意翻译

# 仙人掌女士和她的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)} $ , 通过 $ 400001 $ 条边连接在一起：对每个 $ i $ ， $ (u_{(0, i)}, u_{(1, i)}) $ .换句话说，网格可以被视为"梯子"。  仙人掌女士想知道她是否可以将Cing嵌入到这个网格中，即将仙人掌的每个顶点映射到网格的一个单独的顶点上，而仙人掌每个边将映射到网格中的某个边上。 ## 输入格式 第一行包含一个整数 $ t $ —— 测试用例的数量。 每个测试用例的第一行，包含两个整数 $n$ 和 $m$ —— 分别是给定仙人掌中的顶点数和边数（$1\le n\le 200000$；$0\le m\le 250000$）。 以下 $ m $ 行，每行包含两个整数 $v$ 和 $u$ ，用于描述仙人掌的边缘（$ 1\le v，u\le n，u\ne v $）。 输入中所有 $n$ 的总和不超过 $200000$ 。 ## 输出格式 按照样例输入出现的相同顺序打印每个测试案例的答案。 对于每个测试用例，如果没有合法解，则在第一行打印“No”。 否则，在第一行打印“Yes”，并在下面的 $ n $ 行中描述点的坐标. $ n $ 行中的 第 $ i $ 行 是两个整数 $ x_i $ and $ y_i $ , 第 $ i $ 个点的位置坐标 ( $ 0 \le x_i \le 1 $ ; $ -200\,000 \le y_i \le 200\,000 $ ). ## 样例 #1 ### 样例输入 #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的解释。