A6649 | 「联合省选 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, \ldots, n\}$，$E = \{(p_{a_i}, p_{b_i}) \mid i \in \{1, 2, \ldots, m\}\}$。

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

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

从文件 graperm.in 中读入数据。

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

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

输出到文件 graperm.out 中。

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