题目描述

知名美食家小A被邀请至ATM大酒店，为其品评菜肴。

ATM酒店为小A准备了$n$道菜肴，酒店按照为菜肴预估的质量从高到低给予$1$到$n$的顺序编号，预估质量最高的菜肴编号为$1$。由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有$m$条形如“$i$号菜肴必须先于$j$号菜肴制作”的限制，我们将这样的限制简写为$(i,j)$。现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小A能尽量先吃到质量高的菜肴。也就是说

1.在满足所有限制的前提下，$1$号菜肴“尽量”优先制作；

2.在满足所有限制，$1$号菜肴“尽量”优先制作的前提下，$2$号菜肴“尽量”优先制作；

3.在满足所有限制，$1$号和$2$号菜肴“尽量”优先的前提下，$3$号菜肴“尽量”优先制作；

4.在满足所有限制，$1$号和$2$号和$3$号菜肴“尽量”优先的前提下，$4$号菜肴“尽量”优先制作；

5.以此类推。

现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” （不含引号，首字母大写，其余字母小写）

输入格式

第一行是一个正整数D，表示数据组数。

接下来是D组数据。对于每组数据：

第一行两个用空格分开的正整数$n$和$m$，分别表示菜肴数目和制作顺序限制的条目数。

接下来$m$行，每行两个正整数$x,y$，表示“$x$号菜肴必须先于$y$号菜肴制作”的限制。

注意：$m$条限制中可能存在完全相同的限制。

$1 \le n,m \le 100000,D \le 3$

输出格式

输出文件仅包含$D$行，每行$n$个整数，表示最优的菜肴制作顺序，或者”Impossible!”表示无解（不含引号）。

题目解析

这样的题怎么就轻易地HNOI了呢……（但其实还是有坑点的～）

拓扑排序，但不是字典序最小。

注意到我们可以将图中所有边反向，每次取出入度为0的编号最大的点。这样我们就可以保证编号小的尽量在后面。

最后倒序输出就好啦。时间复杂度$O(n \log n)$。