#2114. 「HNOI2015」菜肴制作

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

ATM 酒店为小 A 准备了 N 道菜肴,酒店按照为菜肴预估的质量从高到低给予 1 N 的顺序编号,预估质量最高的菜肴编号为 1 。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 M 条形如「 i 号菜肴『必须』先于 j 号菜肴制作”的限制」,我们将这样的限制简写为 \langle i,j \rangle

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

  1. 在满足所有限制的前提下, 1 号菜肴「尽量」优先制作;
  2. 在满足所有限制, 1 号菜肴「尽量」优先制作的前提下, 2 号菜肴「尽量」优先制作;
  3. 在满足所有限制, 1 号和 2 号菜肴「尽量」优先的前提下, 3 号菜肴「尽量」优先制作;
  4. 在满足所有限制, 1 号和 2 号和 3 号菜肴「尽量」优先的前提下,4 号菜肴「尽量」优先制作;
  5. 以此类推。

例一:共四道菜肴,两条限制 \langle 3,1 \rangle \langle 4,1 \rangle ,那么制作顺序是 3,4,1,2

例二:共五道菜肴,两条限制 \langle 5,2 \rangle \langle 4,3 \rangle ,那么制作顺序是 1,5,2,4,3

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

例二里,首先制作 1 是不违背限制的;接下来考虑 2 时有 \langle 5,2 \rangle 的限制,所以接下来先制作 5 再制作 2 ;接下来考虑 3 时有 \langle 4,3 \rangle 的限制,所以接下来先制作 4 再制作 3 ,从而最终的顺序是 1,5,2,4,3 。   现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!” (不含引号,首字母大写,其余字母小写)

输入格式

第一行是一个正整数 D ,表示数据组数。
接下来是 D 组数据。 
对于每组数据: 
第一行两个用空格分开的正整数 N M ,分别表示菜肴数目和制作顺序限制的条目数。
接下来 M 行,每行两个正整数 x,y ,表示「 x 号菜肴必须先于 y 号菜肴制作」的限制。(注意: M 条限制中可能存在完全相同的限制)

输出格式

输出文件仅包含 D 行,每行 N 个整数,表示最优的菜肴制作顺序,或者”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

样例解释

第二组数据同时要求菜肴 1 先于菜肴 2 制作,菜肴 2 先于菜肴 3 制作,菜肴 3 先于菜肴 1 制作,而这是无论如何也不可能满足的,从而导致无解。

数据范围与提示

对于 100 \% 的数据, N,M \leq 100000,\ D \leq 3