P3243 [HNOI2015] 菜肴制作
题目描述
知名美食家小 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:共 \(4\) 道菜肴,两条限制 \((3,1)\)、\((4,1)\),那么制作顺序是 \(3,4,1,2\)。
例 2:共 \(5\) 道菜肴,两条限制 \((5,2)\)、\((4,3)\),那么制作顺序是 \(1,5,2,4,3\)。
例 1 里,首先考虑 \(1\),因为有限制 \((3,1)\) 和 \((4,1)\),所以只有制作完 \(3\) 和 \(4\) 后才能制作 \(1\),而根据 3,\(3\) 号又应尽量比 \(4\) 号优先,所以当前可确定前三道菜的制作顺序是 \(3,4,1\);接下来考虑 \(2\),确定最终的制作顺序是 \(3,4,1,2\)。
例 \(2\) 里,首先制作 \(1\) 是不违背限制的;接下来考虑 \(2\) 时有 \((5,2)\) 的限制,所以接下来先制作 \(5\) 再制作 \(2\);接下来考虑 \(3\) 时有 \((4,3)\) 的限制,所以接下来先制作 \(4\) 再制作 \(3\),从而最终的顺序是 \(1,5,2,4,3\)。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible!
(首字母大写,其余字母小写)
输入格式
第一行是一个正整数 \(t\),表示数据组数。接下来是 \(t\) 组数据。对于每组数据:第一行两个用空格分开的正整数 \(n\) 和 \(m\),分别表示菜肴数目和制作顺序限制的条目数。接下来 \(m\) 行,每行两个正整数 \(x,y\),表示 \(x\) 号菜肴必须先于 \(y\) 号菜肴制作的限制。
输出格式
输出文件仅包含 \(t\) 行,每行 \(n\) 个整数,表示最优的菜肴制作顺序,或者 Impossible!
表示无解。
样例 #1
样例输入 #1
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
1 5 3 4 2
Impossible!
1 5 2 4 3
提示
【样例解释】
第二组数据同时要求菜肴 \(1\) 先于菜肴 \(2\) 制作,菜肴 \(2\) 先于菜肴 \(3\) 制作,菜肴 \(3\) 先于。
菜肴 \(1\) 制作,而这是无论如何也不可能满足的,从而导致无解。
【数据范围】
\(100\%\) 的数据满足 \(n,m\le 10^5\),\(1\le t\le 3\)。
\(m\) 条限制中可能存在完全相同的限制。