仙人掌女士非常喜欢她的仙人掌。她特别喜欢一种名叫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 的嵌入。