题目描述

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

输入格式

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

输出格式

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

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

2
1
1
2

提示

【样例解释】 设备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

题目来源

没有写明来源