F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 3331. -- [BeiJing2013]压力

3331: [BeiJing2013]压力

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1341  Solved: 463
[Submit][Status][Discuss]

Description

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的
核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力
之下。
小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的
链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发
送到另一个网络设备。
一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走
的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设
备。
你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有
多少个?

Input

第一行包含3个由空格隔开的正整数N,M,Q。
接下来M行,每行两个整数u,v,表示第u个网络设备(从1开始编号)和
第v个网络设备之间有一个链接。u不会等于v。两个网络设备之间可能有多个
链接。
接下来Q行,每行两个整数p,q,表示第p个网络设备向第q个网络设备发
送了一个数据包。p不会等于q。

Output

输出N行,每行1个整数,表示必须通过某个网络设备的数据包的数量。

Sample Input

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

Sample Output

2
1
1
2

HINT

【样例解释】

设备1、2、3之间两两有链接,4只和1有链接。4想向2和3各发送一个数据

包。显然,这两个数据包必须要经过它的起点、终点和1。

【数据规模和约定】

对于40%的数据,N,M,Q≤2000

对于60%的数据,N,M,Q≤40000

对于100%的数据,N≤100000,M,Q≤200000

Source

[Submit][Status][Discuss]

HOME Back