loj#P2114. 「HNOI2015」菜肴制作

「HNOI2015」菜肴制作

题目描述

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

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

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

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

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

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

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

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

输入格式

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

输出格式

输出文件仅包含 DD 行,每行 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

数据范围与提示

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