零崎的补番计划Ⅲ

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 3 总提交人数: 4

题目描述

现在要补的番也确定了,不过还有个问题。

视频一口气看的太多,难免有些头疼,对于不同的看法,头疼程度自然也是不一样的。

对N个视频V1……Vn,如果任意两个视频i,j连续看有头疼程度e,则用矩阵A[i][j]=e表示。e=-1表示零崎不会连续看这两个视频。

那么零崎如果决定一次看完Vi和Vj最少的头疼程度是多少?(从Vi开始看到Vj结束)

输入

多组测试数据。每组测试数据第一行为两个整数N,Q,代表头疼矩阵的大小和查询次数。

接下来N行每行N个整数,为头疼矩阵。

最后Q行每行2个整数i,j为零崎要看的视频编号。

1<=N,i,j<=500,Q<=20,e<=100

输出

每组一个整数,为能找到的最小头疼程度。

若零崎无论如何也不会从Vi开始看到Vj,则输出jujue(拒绝

输入样例

3 2
-1 0 1 
1 -1 2 
2 3 -1  
1 3
2 2

输出样例

1
jujue

Hint

有向图的算法你们还记得多少?

环路拒绝!

相关推荐