Ikta 对无向图有异常多的依恋。 Ikta-kun 是一个无向图 G 和这两点 s,t对(G,s,t)中,我最喜欢最美的。 组(G,s,t)的“美”就是缘 e = \{u, v\} (u 和 v 是 它仅由 G 在两个不同的点), 在G中 到s我决定将所有值添加到t的最短路径的长度是G至 在带有e的无向图中 它是比到s我决定将所有值添加到t的最短路径长度大 1 的对象数量。
你的工作是 给定(G,s,t),任务是编写一个寻求其“美感”的程序。
输入
输入按以下格式给出。
N M s t
x1 y1
...
xi yi
...
xM yM
首先是无向图中的顶点数、边数以及代表两个顶点的整数。 输入N,M,s,t。 从第二行开始 直到M+1行,输入由边连接的两个顶点。 (但是,G 的顶点集\{1,..., N\}。 )
约束
输入中的每个变量都满足以下约束。 与
2\leq N \leq 100,000
1\leq M \leq 300,000
1\leq s,t,xi,yi \leq N
s 和 t 不同 保证您可以达到
s 我决定将所有值添加到 t 保证你能达到
输出
给定的图表 当G时,设置 一行输出(G,s,t)的“美”。
示例输入 1
3 2 1 3 1 2 2 3
样本输入 1 的输出
1
如果将一条边从顶点 1 延伸到顶点 3,则两点之间的最短距离将缩短 1。
示例输入 2
9 8 7 8 2 6 4 9 8 6 9 2 3 8 1 8 8 5 7 9
样本输入 2 的输出
7
示例输入 3
4 3 1 4 1 2 3 4 4 1
样本输入 3 的输出
0
由于顶点 1 和 4 之间已经存在一条边,因此无法进一步缩短距离。
示例输入 4
9 7 8 9 9 6 6 5 3 6 3 7 2 5 8 5 1 4
样本输入 4 的输出
2