loj#P2114. 「HNOI2015」菜肴制作
「HNOI2015」菜肴制作
题目描述
知名美食家小 A 被邀请至 ATM 大酒店,为其品评菜肴。
ATM 酒店为小 A 准备了 道菜肴,酒店按照为菜肴预估的质量从高到低给予 到 的顺序编号,预估质量最高的菜肴编号为 。由于菜肴之间口味搭配的问题,某些菜肴必须在另一些菜肴之前制作,具体的,一共有 条形如「 号菜肴『必须』先于 号菜肴制作”的限制」,我们将这样的限制简写为 。
现在,酒店希望能求出一个最优的菜肴的制作顺序,使得小 A 能尽量先吃到质量高的菜肴:也就是说,
- 在满足所有限制的前提下, 号菜肴「尽量」优先制作;
- 在满足所有限制, 号菜肴「尽量」优先制作的前提下, 号菜肴「尽量」优先制作;
- 在满足所有限制, 号和 号菜肴「尽量」优先的前提下, 号菜肴「尽量」优先制作;
- 在满足所有限制, 号和 号和 号菜肴「尽量」优先的前提下,4 号菜肴「尽量」优先制作;
- 以此类推。
例一:共四道菜肴,两条限制 、,那么制作顺序是 。
例二:共五道菜肴,两条限制 、,那么制作顺序是 。
例一里,首先考虑 ,因为有限制 和 ,所以只有制作完 和 后才能制作 ,而根据(3), 号又应「尽量」比 号优先,所以当前可确定前三道菜的制作顺序是 ;接下来考虑 ,确定最终的制作顺序是 。
例二里,首先制作 是不违背限制的;接下来考虑 时有 的限制,所以接下来先制作 再制作 ;接下来考虑 时有 的限制,所以接下来先制作 再制作 ,从而最终的顺序是 。
现在你需要求出这个最优的菜肴制作顺序。无解输出“Impossible!
” (不含引号,首字母大写,其余字母小写)
输入格式
第一行是一个正整数 ,表示数据组数。
接下来是 组数据。
对于每组数据:
第一行两个用空格分开的正整数 和 ,分别表示菜肴数目和制作顺序限制的条目数。
接下来 行,每行两个正整数 ,表示「 号菜肴必须先于 号菜肴制作」的限制。(注意: 条限制中可能存在完全相同的限制)
输出格式
输出文件仅包含 行,每行 个整数,表示最优的菜肴制作顺序,或者”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
数据范围与提示
对于 的数据,。