2472 - 【入门】奖金计算

题目描述

A 研究所为表彰为某项目作出贡献的 n 名研究员,决定给他们发放奖金。

研究所请来了几位项目组长,来投票商定奖金的发放。投票方法为,每个组长给出若干意见,每个意见为 2 个整数 x,y ,代表某组长认为 x 号研究员的奖金应当高于 y 号研究员。

请编程计算出:如果最少要发放 100 元奖金,奖金额度须为整数,且满足所有组长意见的前提下,该项目最少要发放多少元奖金?

如果无论如何都无法满足所有组长的意见,请输出impossible

输入

第一行两个整数 n,m,表示待发奖金的研究员的人数和投票意见数;(1≤n≤100001≤m≤20000)

以下 m 行,每行2个整数x,y,表示某个组长认为第 x 号研究员的奖学金应该比第 y 号高。(1≤x,y≤nx!=y

输出

输出最少要发放的奖金额度,如果无论如何都无法满足所有组长的意见,请输出impossible

样例

输入

3 3
2 1
3 1
3 2

输出

303

输入

3 4
2 1
3 1
3 2
2 3

输出

impossible
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
统计
上一题 下一题