Preparing NOJ

商人的宣传

1000ms 65536K

Description:

BruceA州成立了公司,准备宣传活动开始后的第L天到达B州进行新品拍卖,期间Bruce打算将产品拿到各个州去做推销宣传。 K国有很多个州,每个州都与其他一些州相邻,但是K国有规定:

商人只能从某些州到达另外一些州,即连通路线是单向的。

商人不允许在同一个州连续宣传两天或以上,每天宣传完必须离开该州。

商人可以多次来到同一个州进行宣传。

任务:算出AB两州之间的路线的总数。

Input:

第一行包含三个整数n,m,L(1≤n,L≤100),表示n个州、m条通路,L天后必须到达B州。
接下来有m行,每行一对整数x,y(1≤x,y≤n),从x州到y州有通路。
第m+2行:1个整数k,代表有k种询问
第m+3行到m+3+k行:每行两个整数Ai,Bi(1≤Ai,Bi≤n)(1<=i<=k),即每个询问中,Ai、Bi州的位置。

Output:

k个整数t,表示从Ai州到Bi州满足上述规定的路线总数。(<2^31)

Sample Input:

4 5 6
1 2
2 3
3 4
4 1
2 4
1
1 4

Sample Output:

2

Note:

 

本题由旧版NOJ导入,来源:JSOI2010

Info

NOJ

Provider NOJ

Code NOJ1412

Tags

Submitted 6

Passed 3

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet