← 返回题目列表

AtCoder · abc021_c

C. 诚实的高桥君

中文机器翻译题面 查看原题

問題文

你和高桥生活在 AtCoder 王国。 AtCoder 王国有N 连接城镇与城镇 M 有真实的道路,并且可以双向通行。 N 每个城镇都是一个城镇。 它被称为 1,町 2,…,町 N 。 另外,M 每条路都是一条路。 它被称为 1,道路 2,…,道路 M 。

高桥君决定去你家。高桥君是一座城镇 从 a 开始,你将探索AtCoder王国的几个城镇( 镇 途经0 我们已抵达您在 b 的家。

高桥声称走的是最短路线。 高桥很诚实,所以他从不说谎。

你去镇上 a 卡拉町 我决定计算到达 b 的最短路径的数量。答案可能非常大,所以我想与大家分享实际的答案 请打印除以 1,000,000,007(=10^9+7) 后的余数。 到

町 a 卡拉町 我决定计算到达 b 的最短路线是城镇 通往 a 卡拉町 我决定计算到达 b 的路线可最大限度地减少所需道路的数量。


入力

输入将以以下形式从标准输入给出。

N
a b
M
x_1 y_1
x_2 y_2
:
x_M y_M
  • 1 行包含一个整数,表示 AtCoder 王国中存在的城镇数量。 N(2≦N≦100) 被给予。
  • 2 行表示高桥将出发的城镇和您家所在的城镇的号码。 2 整数 a,b(1≦a,b≦N,a≠b) 用空格分隔。
  • 3 行包含一个整数,表示 AtCoder 王国中现有的道路数量。 道路信息在 M(1≦M≦200) 被给予。
  • 4 在 M 行中给出。这几天之一 i(1≦i≦M) 行是一条路 i 并列 2 一镇号 x_i,y_i(1≦x_i,y_i≦N,x_i≠y_i) 用空格分隔。
  • 您可以沿着几条道路从任何城镇前往任何其他城镇。 在

出力

1 线上,镇 到 a 卡拉町 我决定计算到达 b 的最短路径的数量是 1,000,000,007 后的余数。 到

不要忘记最后的换行符。


入力例1

7
1 7
8
1 2
1 3
4 2
4 3
4 5
4 6
7 5
7 6

出力例1

4

此示例输入的图如下,具有最短路径: 4 是可能的。

  • 1→2→4→5→7
  • 1→3→4→5→7
  • 1→2→4→6→7
  • 1→3→4→6→7


入力例2

7
1 7
9
1 2
1 3
4 2
4 3
4 5
4 6
7 5
7 6
4 7

出力例2

2

此示例输入的图表如下。