CF1578C.Cactus Lady and her Cing

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.

仙人掌女士非常喜爱她的仙人掌们，尤其是她心爱的小仙人掌“青”。青可以被看作一个连通的无向图，其中每个顶点至多位于一个简单环上。直观地说，仙人掌是树的一种推广，允许存在若干环；但不允许重边（一对顶点间存在多条边）和自环（连接一个顶点到其自身的边）。

她为心爱的小仙人掌青购置了一块特殊的网格。该网格可表示为一张图：它由两条长度均为 $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$）将这两条路径连接起来。换言之，该网格可视作一架梯子。

仙人掌女士想知道：能否将青嵌入该网格中？即，是否能将仙人掌的每个顶点一一映射到网格的不同顶点上，并使得仙人掌的每条边均映射为网格中的一条边？

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$.

第一行包含一个整数 $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$。

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$).

按输入中测试用例出现的相同顺序，为每个测试用例输出一个答案。

对于每个测试用例，若不存在满足要求的布局，则在第一行输出“No”。

否则，在第一行输出“Yes”，并在接下来的 $n$ 行中描述该布局。其中第 $i$ 行（这 $n$ 行中的第 $i$ 行）应包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个顶点的位置（满足 $0 \le x_i \le 1$；$-200\,000 \le y_i \le 200\,000$）。

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.

测试用例之间的空行仅为提高可读性。在实际的测试用例中，不存在空行。

在本说明中，我们考虑测试 2 和测试 4 的嵌入（embedding）。

我们首先给出测试 2 的嵌入。

接下来是测试 4 的嵌入。