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