Public Judge

pjudge

Time Limit: 10 s Memory Limit: 2048 MB Total points: 100 Hackable ✓

# 21780. 【PR #11】复原

统计

对于无向图 $G = ⟨V, E⟩$,它的线图 $L(G)$ 也是一个无向图:

  • 它的点集大小为 $E$,每个点唯一对应着原图的一条边。
  • 两个点之间有边当且仅当这两个点对应的边在原图上有公共点(注意不会有自环)。
problem_21780_1.png

现在,给定一张 $n$ 个点 $m$ 条边的简单无向图 $G$ (不保证连通),你需要构造一张 $n'$ 个点 $n$ 条边的简单无向图 $H$,使得 $L(H) = G$。

输入格式

输入包含多组数据。

输入的第一行包含一个整数 $T$,表示数据组数。对于每组数据:

输入的第一行包含两个整数 $n, m$。

接下来 $m$ 行,每行两个整数 $u,v$,描述一条边。

数据保证 $\sum n \leq 3 \times 10^5, \sum m \leq 3 \times 10^6$。

输出格式

对于每组数据,如果不存在对应的 $H$,则输出一行 No

否则,输出一行 Yes,接下来一行包含两个整数 $n', m'$,分别表示 $H$ 的点数和边数。

接下来 $m'$ 行,每行两个整数 $u,v$,描述一条边。

你必须保证 $1 \leq n' \leq 10^6$ 且 $m'=n$,且边按照点的编号顺序来输出。

如果有多种合法的输出,你可以输出任何一种。

样例数据

样例 1 输入

5
1 0
2 1
1 2
3 3
1 2
1 3
2 3
4 3
1 2
1 3
1 4
5 6
1 2
2 3
2 4
3 4
3 5
4 5

样例 1 输出

Yes
2 1
1 2
Yes
3 2
1 2
2 3
Yes
3 3
1 2
1 3
2 3
No
Yes
5 5
4 5
3 4
1 3
2 3
1 2

样例 2

见下发文件。

本组样例满足子任务 2 的特殊限制。

样例 3

见下发文件。

本组样例满足子任务 3 的特殊限制。

样例 4

见下发文件。

本组样例满足子任务 4 的特殊限制。

样例 5

见下发文件。

本组样例满足子任务 5 的特殊限制。

样例 6

见下发文件。

本组样例满足子任务 6 的特殊限制。

样例 7

见下发文件。

本组样例满足子任务 7 的特殊限制。

样例 8

见下发文件。

本组样例满足子任务 8 的特殊限制。

样例 9

见下发文件。

本组样例满足子任务 9 的特殊限制。

样例 10

见下发文件。

本组样例满足子任务 10 的特殊限制。

样例 11

见下发文件。

本组样例满足子任务 11 的特殊限制。

子任务

对于所有数据,$1 \leq n, \sum n \leq 3 \times 10^5$,$0 \leq m, \sum m \leq 3 \times 10^6$,$1 \leq T \leq 3 \times 10^5$。

子任务编号 $n \leq $ 特殊性质 分值
$1$ $4$ $4$
$2$ $5$ $4$
$3$ $6$ $4$
$4$ $7$ $4$
$5$ $8$ $4$
$6$ $20$ $10$
$7$ $200$ $15$
$8$ $2 \times 10^4$ A $10$
$9$ $15$
$10$ $3 \times 10^5$ A $10$
$11$ $20$

下面是一些额外说明:

  • (性质 A):保证所有数据均有解,且存在一张符合要求的图 $H$ 满足 $H$ 是一棵树。

时间限制:$\texttt{10s}$

空间限制:$\texttt{2048MB}$