题目描述

如今，路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理 $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\le 2000$
• 对于 $60\%$ 的数据，$N,M,Q \le 40000$
• 对于 $100\%$ 的数据，$N \le 100000$，$M,Q \le 200000$。