[IOI2009] Regions

## 滥用本题评测将被封号 IOI2009 D2T3 原题时间限制 8s，为节约评测资源，时间限制改为 4s。

联合国区域发展委员会（The United Nations Regional Development Agency, UNRDA）有一个良好的组织结构。它任用了 $N$ 名委员，每名委员都属于几个地区中的一个。委员们按照其资历被编号为 $1$ 到 $N$ ，$1$ 号委员是主席，资历最高。委员所属地区被编号为 $1$ 到 $R$。除了主席之外所有委员都有一个直接导师。任何直接导师的资历都比他所指导的委员的资历要高。 我们称委员 $A$ 是委员 $B$ 的导师当且仅当 $A$ 是 $B$ 的直接导师或者 $A$ 是 $B$ 的直接导师的导师。显然，主席是所有其他委员的导师，没有任何两名委员互为导师。 现在，为了调查大量对 UNRDA 偏向某些地区的不平衡的组织结构的指控，UNRDA 想要建立一个计算机系统：在给定委员之间的直接导师关系的情况下，该系统可以回答下述形式的问题：给定两个地区 $r_1$ 和 $r_2$，要求系统回答委员会中有多少对委员 $e_1$ 和 $e_2$，满足 $e_1$ 属于 $r_1$，而 $e_2$ 属于 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。每次询问都有两个参数 $r_1$ 和 $r_2$，结果是一个整数：满足上述条件的 $(e_1, e_2)$ 二元组的数量。 **任务**：编写一个程序，给定每个委员的地区和直接导师，**在线** 回答上述询问。 **强制在线将以交互的格式进行**。

第一行包含三个整数 $N, R, Q$，分别由一个空格隔开，分别表示雇员人数，区域数和查询数。 接下来 $N$ 行按照资历的顺序给出了 $N$ 个委员的描述信息。其中第 $k$ 行描述了编号为 $k$ 的委员。第一行（描述主席的一行）包含一个整数：主席所属的地区 $H_1$。其余的 $N - 1$ 行，每行包含两个整数，以一个空格隔开分别表示委员 $k$ 的直接导师 $S_k$ 和委员 $k$ 所属的地区 $H_k$。 ### 交互格式 在读入所有输入数据之后，你的程序必须依次从标准输入中读入询问，并将询问结果输出至标准输出。必须依次回答 $Q$ 个询问，每次回答一个。**在读入下一个询问之前，你必须先回答当前询问**。 每个询问是标准输入的一行，用两个不同整数 $r_1, r_2$ 表示。

对查询的回答是标准输出的一行，包含一个整数，表示在 UNRDA 中有多少对委员 $e_1$ 和 $e_2$ 满足下述条件：$e_1$ 属于地区 $r_1$，$e_2$ 属于地区 $r_2$，并且 $e_1$ 是 $e_2$ 的导师。 **注意**：输入数据保证给出的任意询问的正确答案小于 $10 ^ 9$。 **特别注意**：为了正确地和交互库交互，你的程序必须 **在回答每次询问后刷新标准输出缓冲区**。你同样需要避免意外地在读入标准输入时堵住了输入流，这有可能在你使用 `scanf("%d\n", ...)` 的语句时发生。 你可以使用如下语句来清空缓冲区： - 对于 C/C++：`fflush(stdout)`； - 对于 C++：`std::cout << std::flush`； - 对于 Java：`System.out.flush()`； - 对于 Python：`stdout.flush()`； - 对于 Pascal：`flush(output)`； - 对于其他语言，请自行查阅对应语言的帮助文档。 特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2

1 3

2 3

3 1

1 [刷新缓冲区]

3 [刷新缓冲区]

2 [刷新缓冲区]

1 [刷新缓冲区]

### 数据范围与约定 - 对于 $30\%$ 的数据，$N\leq 500$。 - 对于 $55\%$ 的数据，没有地区包含超过 $500$ 个委员。 - 同时满足上述两个条件的数据有 $15\%$，至少满足上述一个条件的数据有 $70\%$。 - 对于 $100\%$ 的数据，$1 \le N, Q \le 2 \times 10^5$，$1 \le H_k, r_1, r_2 \le R \le 2.5 \times 10^4$，$1 \le S_k < k$。