【统一省选2025】图排列 - 题目

小 Q 有 $m$ 个互不相同的正整数二元组 ${(a_{i}, b_{i})}_{i = 1}^{m}$ ，其中对于所有 $1 \leq i \leq m$ ， $1 \leq a_{i} < b_{i} \leq n$ 。这 $m$ 个二元组满足如下性质：不存在 $1 \leq i, j \leq n$ 满足 $a_{i} < a_{j} < b_{i} < b_{j}$ 。

小 D 有一个 $1 \sim n$ 的排列 $p$ 。小 Q 和小 D 利用他们手上的二元组和排列一起构建了一张 $n$ 个点 $m$ 条边的无向图 $G = (V, E)$ ，其中 $V = {1, 2, \dots, n}$ ， $E = {(p_{a_{i}}, p_{b_{i}}) ∣ i \in {1, 2, \dots, m}}$ 。

现在小 I 得知了图 $G$ ，他想要知道在小 Q 的 $m$ 个二元组所具有的性质的前提下，小 D 手中的排列 $p$ 可能是什么。由于小 I 手中的信息不足，排列 $p$ 有很多种可能，小 I 希望你可以告诉他其中字典序最小的那一个。

小 Q，小 D 和小 I 是很好的朋友，他们保证不会欺骗彼此，因此存在至少一个排列 $p$ 满足条件。

输入格式

本题有多组测试数据。输入的第一行两个整数 $c, T$ ，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 $c = 0$ 。

对于每组测试数据，第一行两个整数 $n, m$ ，分别表示图 G 的点数和边数，接下来 $m$ 行，第 $i (1 \leq i \leq m)$ 行两个整数 $u_{i}, v_{i}$ ，描述图 $G$ 的一条边。

输出格式

对于每组测试数据，输出一行一个 $1 \sim n$ 的排列 $p$ ，表示题设条件下字典序最小的排列。数据保证存在至少一个排列 $p$ 满足条件。

输入输出样例 #1

输入 #1

输出 #1

1 2 4 3
1 3 2 4

说明/提示

【样例 1 解释】

该组样例共有 $2$ 组测试数据。

对于第一组测试数据，
- 如果小 D 的排列为 $[1, 2, 3, 4]$ ，那么小 Q 拥有的二元组为 ${(1, 3), (2, 4)}$ ，但取 $i = 1, j = 2$ 有 $1 < 2 < 3 < 4$ ，因此不满足小 Q 的二元组的性质。
- 如果小 D 的排列为 $[1, 2, 4, 3]$ ，那么小 Q 拥有的二元组为 ${(1, 4), (2, 3)}$ ，可以证明其满足性质。
对于第二组测试数据，如果小 D 的排列为 $[1, 3, 2, 4]$ ，那么小 Q 拥有的二元组为 ${(2, 3), (3, 4), (1, 2), (1, 4), (2, 4)}$ ，可以证明其满足性质。

【样例 2】

见选手目录下的 graperm/graperm2.in 与 graperm/graperm2.ans。

该组样例满足测试点 $1, 2$ 的限制。

【样例 3】

见选手目录下的 graperm/graperm3.in 与 graperm/graperm3.ans。

该组样例满足测试点 $3, 4$ 的限制。

【样例 4】

见选手目录下的 graperm/graperm4.in 与 graperm/graperm4.ans。

该组样例满足测试点 $5, 6$ 的限制。

【样例 5】

见选手目录下的 graperm/graperm5.in 与 graperm/graperm5.ans。

该组样例满足测试点 $7, 8$ 的限制。

【样例 6】

见选手目录下的 graperm/graperm6.in 与 graperm/graperm6.ans。

该组样例满足测试点 $9 \sim 11$ 的限制。

【样例 7】

见选手目录下的 graperm/graperm7.in 与 graperm/graperm7.ans。

该组样例满足测试点 $12$ 的限制。

【样例 8】

见选手目录下的 graperm/graperm8.in 与 graperm/graperm8.ans。

该组样例满足测试点 $13 \sim 15$ 的限制。

【样例 9】

见选手目录下的 graperm/graperm9.in 与 graperm/graperm9.ans。

该组样例满足测试点 $16 \sim 18$ 的限制。

【样例 10】

见选手目录下的 graperm/graperm10.in 与 graperm/graperm10.ans。

该组样例满足测试点 $19 \sim 21$ 的限制。

【样例 11】

见选手目录下的 graperm/graperm11.in 与 graperm/graperm11.ans。

该组样例满足测试点 $22 \sim 25$ 的限制。

【子任务】

对于所有测试点，

$1 \leq T \leq 10$ ，
$2 \leq n \leq 10^{5}$ ， $0 \leq m \leq 2 n$ ，
$\forall 1 \leq i \leq m$ ， $1 \leq u_{i}, v_{i} \leq n$ ， $u_{i} \neq v_{i}$ ，即 $G$ 没有自环，
$\forall 1 \leq i < j \leq m$ ， ${u_{i}, v_{i}} \neq {u_{j}, v_{j}}$ ，即 $G$ 没有重边，
保证存在至少一个排列 $p$ 满足条件。

测试点编号	$n \leq$	特殊性质
$1, 2$	$10$	无
$3, 4$	$2 000$	AC
$5, 6$	$2 000$	A
$7, 8$	$2 000$	C
$9 \sim 11$	$2 000$	无
$12$	$10^{5}$	ABC
$13 \sim 15$	$10^{5}$	AC
$16 \sim 18$	$10^{5}$	A
$19 \sim 21$	$10^{5}$	C
$22 \sim 25$	$10^{5}$	无

特殊性质 A： $G$ 连通。
特殊性质 B： $G$ 中每个点的度数不超过 $2$ 。
特殊性质 C： $G$ 中不存在简单环，即 $G$ 是一个森林。

时间限制：2s

空间限制：512MB

Universal Online Judge

UOJ