[THUWC 2020] 道路修建

$A$ 国是一个古老的国家。这个国家分布着 $n$ 个城市，城市由 $1 \sim n$ 编号。其中，$1$ 号城市是这个国家的首都，也是国家里唯一有港口的城市。进口的货物从首都的港口运入，再运送向其它城市。 为了方便进口货物的运送，$A$ 国国王打算修建若干条单向道路专门用于运送货物。很快，$A$ 国的大臣们给出了一个道路修建方案：这个方案由 $m$ 条单向道路组成，通过这些道路可以从 $1$ 号城市到达国家内的其它任意一个城市。非常特殊的是，这 $m$ 条道路构成的道路网络不存在环。 由于财政状况不允许，$A$ 国国王打算从 $m$ 条道路中先选择 $n-1$ 条进行修建，以保证基本的货物运输能力。他使用了一种类似于深度优先搜索的方法确定出优先修建的 $n-1$ 条道路： 首先，令集合 $S$ 为仅包含 $1$ 号城市的集合，并设置当前城市 $u$ 为 $1$ 号城市。 然后，选择一条以当前城市 $u$ 为出发点、一个不在集合 $S$ 内的城市 $v$ 为终点的道路，将该道路标记为优先修建的道路，将城市 $v$ 加入 $S$ 集合，并将城市 $v$ 的父亲设置为当前城市 $u$。 最后，将当前城市 $u$ 修改为城市 $v$。如果城市 $v$ 的选择有多个，则选择城市编号最小的一个；如果没有可以选择的城市 $v$，则将当前城市 $u$ 修改为 $u$ 的父亲。 重复上述操作，直到所有城市被加入 $S$ 集合时停止。 可以发现，上述步骤恰好可以选出被优先修建的 $n - 1$ 条道路，并且这些优先修建的道路可以构成一个以首都为根的树型结构。我们称这些被优先修建的道路为树上道路。 随着经济的发展，$A$ 国逐渐完成了 $m$ 条道路构成的道路网。但其中，树上道路由于修建年代较早，时常需要进行维护。$A$ 国的大臣们提出了 $q$ 个可能的维护计划，每个修建计划需要同时维护城市 $a$ 与城市 $b$ 之间的所有树上道路，并且保证城市 $a$ 是城市 $b$ 在树上的祖先。这样的维护计划会对城市 $b$ 为根的子树产生很大的影响，$A$ 国国王希望你帮忙评估每个可能的维护计划——计算在城市 $a$ 与城市 $b$ 之间的所有树上道路不能使用时，从首都出发，有多少个在以城市 $b$ 为根的子树内的城市将不能到达？ ## Input 第一行三个整数 $n,m,q$，分别表示 $A$ 国的城市数量、道路修建方案的道路数量、维护计划的数量。 接下来 $m$ 行，每行两个整数 $x, y$，表示修建方案中一条从$x$到$y$的单向道路。 接下来 $q$ 行，每行两个整数 $a,b$，表示一个维护计划。 输入数据保证： 1. 给定的道路修建方案保证从首都出发能到达 $A$ 国的每个城市，并且该方案中不存在环。 2. 任意两个城市之间的道路至多出现一条，每条道路两端的城市编号不同。 3. 每个维护计划中的城市 $a$ 保证是城市 $b$ 在树上道路构成的树结构中的某个祖先。 ## Output 输出 $q$ 行，每行一个整数，表示在每个维护计划下，从首都出发，有多少个在以城市 $b$ 为根的子树内的城市将不能到达。 [samples] ## Note **【子任务】** |子任务编号|分值|特殊限制| |:----:|:----:|:----:| |$1$|$20$|$n,q\leq 1000$，$m\leq 1500$| |$2$|$23$|保证维护计划的城市 $a$ 是城市 $b$ 的父亲| |$3$|$11$|$m=n$| |$4$|$19$|保证维护计划满足 $a=1$| |$5$|$27$|无| 对于 $100\%$ 的数据，满足 $1\leq n,q \leq 10 ^ 5$，$1\leq m \leq 1.5 \times 10 ^ 5$。