OpenJudge

E:人在~囧途

总时间限制:
1000ms
内存限制:
66566kB
描述

春节结束了,许多小伙伴都要返校了,然而这个时候正是返校的高峰期,“千金易得,一票难求”,许多小伙伴都深陷买不到票的苦恼当中,asdfgh也没能逃过这一劫,于是asdfgh决定先乘车到另一个城市,然后再换乘,不过asdfgh也不确定那个城市有没有票,所以asdfgh希望能知道更多的到达目的地的方案,不过asdfgh过年吃的太好,现在满脑肥油,已经不能思考了,所以现在请你来帮助asdfgh找出有多少种到达目的地方案。现在asdfgh通过交易知道了n个城市的交通信息(城市编号从0 —— n-1),asdfgh所在的城市编号为0 目的地城市编号为n-1,然后知道n个城市的连通情况,现在请你告诉asdfgh在换乘k次的情况下,有多少种到达目的地方案。

输入
首先输入两个整数 n, m(2<=n<=20,1<=m<=n*n-1)
n表示有n个城市,接下来有m行,每一行有两个整数a,b 表示城市a到城市b可以买到票(注意是单向的)
接下来一个整数t,表示接下来有t组询问,每组询问输入一个整数q,表示如果换乘q次到达目的地有多少种方案(方案数对1000取余)tip:有可能asdfgh能买到直达票哦!!asdfgh可能会走同一条路线多次,也有可能在终点换乘,只需要保证换乘次数就可以了
输出
输出一个整数对1000取余的方案数
样例输入
4 4
0 1
0 3
0 2
1 3
2
0
1
样例输出
1
1
提示
有可能asdfgh能买到直达票哦!!asdfgh可能会走同一条路线多次,也有可能在终点换乘,只需要保证换乘次数就可以了
来源
秦亮
全局题号
13302
提交次数
0
尝试人数
0
通过人数
0