Bajtazar 是 BajtKom 公司的管理员。公司共有 $n$ 台服务器，服务器之间的连接网络呈树状拓扑结构，即从任意一台服务器到另一台服务器都有且仅有一条路径（无环）。

最近，Bajtazar 面临着来自敌国 Bitocja 的黑客攻击，导致公司网络中出现了计算机病毒。每个病毒都有一个特定的影响范围 $d$。当一个影响范围为 $d$ 的病毒攻击某台服务器时，它会干扰该服务器以及所有与该服务器距离不超过 $d$ 的服务器的正常工作。

Bajtazar 有一个杀毒程序。在某台服务器上运行该程序会清除该服务器上的所有病毒。特别地，这意味着这些病毒将不再干扰之前受其影响的服务器。遗憾的是，Bajtazar 的杀毒程序无法提供永久保护：一旦服务器被清除病毒，如果再次受到病毒攻击，它会再次被感染。

你的任务是编写一个库，帮助收集 BajtKom 网络的安全数据。该库将接收关于病毒攻击和运行杀毒程序的信息，并需要报告在给定服务器对之间发送消息时的风险。风险定义为通信路径上（包括起始和目标服务器）受病毒干扰的服务器数量。

最后，公司连接服务器的电缆年代久远，容易丢失信号强度。因此，通信仅限于长度不超过 500 的路径（这也是病毒的最大影响范围和通信的最大距离）。

交互

在本题中，你需要编写一个 C++ 库，与评测程序进行交互。你的库必须提供（实现）以下函数，这些函数将由评测程序调用（如果需要，你的解决方案也可以包含其他函数）：

• inicjuj(n) 该函数在程序开始时仅被调用一次。它的调用通知库服务器的数量 $n$。服务器编号从 $1$ 到 $n$。 – C++: void inicjuj(int n);

• polaczenie(a, b) 该函数将在 inicjuj 函数调用后被直接调用 $n - 1$ 次。它的调用通知库服务器 $a$ 和 $b$ 之间存在直接连接。你将准确地获知每一个直接连接的存在。 – C++: void polaczenie(int a, int b);

• wirus(a, d) 调用此函数通知库，病毒感染了编号为 $a$ ($1 \le a \le n$) 的服务器，并开始干扰所有距离该服务器不超过 $d$ ($0 \le d \le 500$) 个直接连接的服务器。 – C++: void wirus(int a, int d);

• antywirus(a) 调用此函数通知库，杀毒程序清除了编号为 $a$ ($1 \le a \le n$) 的服务器上的所有病毒。 – C++: void antywirus(int a);

• ryzyko(a, b) 此函数是库关于通信风险的查询。调用它应返回连接服务器 $a$ 和 $b$ ($1 \le a, b \le n, a \neq b$) 的路径上受病毒干扰的服务器数量。你可以假设该路径包含不超过 500 个直接连接。 – C++: int ryzyko(int a, int b);

你的程序不得读取任何数据（无论是从标准输入还是从文件）。它也不得向文件或标准输出写入任何内容。它可以写入标准诊断输出 (stderr) —— 但请记住，这会消耗宝贵的时间。也不要声明 main 函数。

编译与运行

你的库 sie.cpp 将使用以下命令与评测程序一起编译：

g++ -O3 -static sie.cpp siegrader.cpp -std=c++17

样例

网络拓扑结构

输入格式 1

inicjuj(5)
polaczenie(1, 2)
polaczenie(2, 3)
polaczenie(3, 4)
polaczenie(2, 5)
wirus(5, 1)
ryzyko(1, 3)
wirus(1, 2)
ryzyko(1, 3)
antywirus(1)
ryzyko(1, 3)
wirus(5, 0)
ryzyko(1, 3)
ryzyko(3, 4)

输出格式 1

1
3
1
1
0

Eksperymenty

为了方便测试，我们提供了 siegrader.cpp 作为示例评测程序。你可以将你的 sie.cpp 放在同一文件夹下进行编译。

你可以使用 make 命令通过提供的 makefile 生成可执行文件 sieCPP.e。该程序从标准输入读取函数调用序列，并输出 ryzyko 函数的返回值。输入格式为：第一行包含调用次数 $m$，随后 $m$ 行每行以字符 i, p, w, a, r 开头，分别对应 inicjuj, polaczenie, wirus, antywirus, ryzyko 函数，后跟相应的参数。

Ocenianie

令 $q$ 表示 wirus、antywirus 和 ryzyko 函数调用的总次数。在所有子任务中，满足 $1 \le n \le 1\,000\,000$ 且 $1 \le q \le 100\,000$。病毒的影响范围以及 ryzyko 函数中服务器之间的路径长度不超过 500。