CF1578C 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的解释。
