UOJ Logo Universal Online Judge

UOJ

#470. 【ZJOI2019】语言

附件下载 统计

九条可怜是一个喜欢规律的女孩子。按照规律,第二题应该是一道和数据结构有关的题。

在一个遥远的国度,有 n 个城市。城市之间有 n1 条双向道路,这些道路保证了任何两个城市之间都能直接或者间接地到达。

在上古时代,这 n 个城市之间处于战争状态。在高度闭塞的环境中,每个城市都发展出了自己的语言。而在王国统一之后,语言不通给王国的发展带来了极大的阻碍。为了改善这种情况,国王下令设计了 m 种通用语,并进行了 m 次语言统一工作。在第 i 次统一工作中,一名大臣从城市 si 出发,沿着最短的路径走到了 ti,教会了沿途所有城市(包括 si,ti) 使用第 i 个通用语。

一旦有了共通的语言,那么城市之间就可以开展贸易活动了。两个城市 ui,vi 之间可以开展贸易活动当且仅当存在一种通用语 L满足 uivi 最短路上的所有城市(包括 ui,vi),都会使用 L

为了衡量语言统一工作的效果,国王想让你计算有多少对城市(u,v)(u<v),他们之间可以开展贸易活动。

输入格式

第一行输入两个正整数 n,m,表示城市数和通用语的数量。

接下来 n1 行,每行两个整数 xi,yi(1xi,yin),表示了一条连接城市 xi,yi 的道路。

接下来 m 行,每行两个整数 si,ti(1si,tin,siti),表示一次语言普及工作。

输出格式

输出一行一个整数,表示可以开展贸易活动的城市对数量。

样例一

input

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

output

8

explanation

可以开展贸易活动的城市对为 (1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5)

样例二

见样例数据下载

限制与约定

对于 100% 的数据,有 1si,yi,si,tin,m1,siti,xiyi

测试点 n m 其他限制
1 300 300
2
3 5000 5000
4
5 105 105 yi=xi+1
6
7
8
9
10

时间限制3s

空间限制512MB

下载

样例数据下载