Description

如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的

核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力

之下。

小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的

链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发

送到另一个网络设备。

一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走

的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设

备。

你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有

多少个?

Format

Input

第一行包含3个由空格隔开的正整数N,M,Q。

接下来M行,每行两个整数u,v,表示第u个网络设备(从1开始编号)和

第v个网络设备之间有一个链接。u不会等于v。两个网络设备之间可能有多个

链接。

接下来Q行,每行两个整数p,q,表示第p个网络设备向第q个网络设备发

送了一个数据包。p不会等于q。

Output

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

Samples

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

2
1
1
2

Limitation

【样例解释】

设备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