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)}$，此外对于每个 $i$，还有 $400\,001$ 条连接 $(u_{(0, i)}, u_{(1, i)})$ 的边。换句话说，该网格可以看作一个梯子。  仙人掌女士想知道她能否将 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$。

按输入中出现的顺序，为每个测试用例输出答案。 对于每个测试用例，如果不存在这样的嵌入，则在第一行输出 "No"。 否则，在第一行输出 "Yes"，并在接下来的 $n$ 行描述嵌入方案。这 $n$ 行中的第 $i$ 行应包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个顶点的位置（$0 \le x_i \le 1$；$-200\,000 \le y_i \le 200\,000$）。

测试用例之间的空行仅为清晰起见。在实际的测试用例中没有空行。 在注释中，我们考虑测试 2 和测试 4 的嵌入。 以下是测试 2 的嵌入。  以下是测试 4 的嵌入。  翻译由 DeepSeek V3.2 完成