P12114 [NWRRC2024] Just Half is Enough

Jacob 正在学习图论。今天他了解到，有向图的 *拓扑排序* 是指对图中顶点的一个线性排序，使得对于图中的每一条有向边 $(u, v)$，$u$ 在排序中总是位于 $v$ 之前。 众所周知，拓扑排序仅适用于无环图。那么我们如何将这个概念推广到任意图呢？ Jacob 提出了 _半拓扑排序_ 的概念：图的顶点的一个线性排序，使得 **至少一半** 的有向边 $(u, v)$ 满足 $u$ 在排序中位于 $v$ 之前。 换句话说，如果图有 $m$ 条边，对于某个排序，有 $k$ 条边满足上述条件，则当 $k \ge \lceil \frac{m}{2} \rceil$ 时，该排序被称为 *半拓扑排序*。 请帮助 Jacob 找出给定图的任意一个半拓扑排序，或者报告不存在这样的排序。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和边数（$2 \le n \le 10^5$；$1 \le m \le 2 \cdot 10^5$）。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，描述一条从顶点 $u_i$ 到顶点 $v_i$ 的有向边（$1 \le u_i, v_i \le n$；$u_i \ne v_i$）。图中不包含重边：每条有向边 $(u, v)$ 最多出现一次。但是，同时存在边 $(u, v)$ 和 $(v, u)$ 是允许的。 保证所有测试用例的 $n$ 之和不超过 $10^5$，$m$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果不存在满足条件的半拓扑排序，则输出单个整数 $-1$。 否则，输出 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$，表示图的排序（$1 \le p_i \le n$）。对于至少 $\lceil \frac{m}{2} \rceil$ 条边 $(u_i, v_i)$，整数 $u_i$ 必须位于整数 $v_i$ 之前。如果有多个解，输出任意一个即可。