UOJ Logo Universal Online Judge

UOJ

#954. 【统一省选2025】图排列

附件下载 统计

小 Q 有 m 个互不相同的正整数二元组 {(ai,bi)}i=1m,其中对于所有 1im1ai<bin。这 m 个二元组满足如下性质:不存在 1i,jn 满足 ai<aj<bi<bj

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

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

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

输入格式

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

对于每组测试数据,第一行两个整数 n,m,分别表示图 G 的点数和边数,接下来 m 行,第 i(1im) 行两个整数 ui,vi,描述图 G 的一条边。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1 2 4 3
1 3 2 4

说明/提示

【样例 1 解释】

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

  • 对于第一组测试数据,
    • 如果小 D 的排列为 [1,2,3,4],那么小 Q 拥有的二元组为 {(1,3),(2,4)},但取 i=1,j=21<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。

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

【样例 7】

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

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

【样例 8】

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

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

【样例 9】

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

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

【样例 10】

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

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

【样例 11】

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

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

【子任务】

对于所有测试点,

  • 1T10
  • 2n1050m2n
  • 1im1ui,vinuivi,即 G 没有自环,
  • 1i<jm{ui,vi}{uj,vj},即 G 没有重边,
  • 保证存在至少一个排列 p 满足条件。
测试点编号 n 特殊性质
1,2 10
3,4 2000 AC
5,6 2000 A
7,8 2000 C
911 2000
12 105 ABC
1315 105 AC
1618 105 A
1921 105 C
2225 105
  • 特殊性质 A:G 连通。
  • 特殊性质 B:G 中每个点的度数不超过 2
  • 特殊性质 C:G 中不存在简单环,即 G 是一个森林。

时间限制:2s

空间限制:512MB