#P3243. [HNOI2015] 菜肴制作

[HNOI2015] 菜肴制作

题目描述

知名美食家小 A 被邀请至 ATM 大酒店,为其品评菜肴。ATM 酒店为小 A 准备了 nn 道菜肴,酒店按照为菜肴预估的质量从高到低给予 11nn 的顺序编号,预估质量最高的菜肴编号为 11

由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 mm 条形如 ii 号菜肴必须先于 jj 号菜肴制作的限制,我们将这样的限制简写为 (i,j)(i,j)

现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A 能尽量先吃到质量高的菜肴:

也就是说,

  1. 在满足所有限制的前提下,11 号菜肴尽量优先制作。

  2. 在满足所有限制,11 号菜肴尽量优先制作的前提下,22 号菜肴尽量优先制作。

  3. 在满足所有限制,11 号和 22 号菜肴尽量优先的前提下,33 号菜肴尽量优先制作。

  4. 在满足所有限制,11 号和 22 号和 33 号菜肴尽量优先的前提下,44 号菜肴尽量优先制作。

  5. 以此类推。

例 1:共 44 道菜肴,两条限制 (3,1)(3,1)(4,1)(4,1),那么制作顺序是 3,4,1,23,4,1,2

例 2:共 55 道菜肴,两条限制 (5,2)(5,2)(4,3)(4,3),那么制作顺序是 1,5,2,4,31,5,2,4,3

例 1 里,首先考虑 11,因为有限制 (3,1)(3,1)(4,1)(4,1),所以只有制作完 3344 后才能制作 11,而根据 3,33 号又应尽量比 44 号优先,所以当前可确定前三道菜的制作顺序是 3,4,13,4,1;接下来考虑 22,确定最终的制作顺序是 3,4,1,23,4,1,2

22 里,首先制作 11 是不违背限制的;接下来考虑 22 时有 (5,2)(5,2) 的限制,所以接下来先制作 55 再制作 22;接下来考虑 33 时有 (4,3)(4,3) 的限制,所以接下来先制作 44 再制作 33,从而最终的顺序是 1,5,2,4,31,5,2,4,3。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!(首字母大写,其余字母小写)

输入格式

第一行是一个正整数 tt,表示数据组数。接下来是 tt 组数据。对于每组数据:第一行两个用空格分开的正整数 nnmm,分别表示菜肴数目和制作顺序限制的条目数。接下来 mm 行,每行两个正整数 x,yx,y,表示 xx 号菜肴必须先于 yy 号菜肴制作的限制。

输出格式

输出文件仅包含 tt 行,每行 nn 个整数,表示最优的菜肴制作顺序,或者 Impossible! 表示无解。

3
5 4
5 4
5 3
4 2
3 2
3 3
1 2
2 3
3 1
5 2
5 2
4 3
1 5 3 4 2 
Impossible! 
1 5 2 4 3

提示

【样例解释】

第二组数据同时要求菜肴 11 先于菜肴 22 制作,菜肴 22 先于菜肴 33 制作,菜肴 33 先于。

菜肴 11 制作,而这是无论如何也不可能满足的,从而导致无解。

【数据范围】

100%100\% 的数据满足 n,m105n,m\le 10^51t31\le t\le 3

mm 条限制中可能存在完全相同的限制。