Bajtazar is an administrator at the BajtKom company. The company has $n$ servers, and the network of connections between them has a tree topology, meaning that any server can send a message to any other server (directly or indirectly) using exactly one path (without backtracking).

Recently, a major challenge for Bajtazar has been computer viruses that appear in the company network as a result of hacker attacks from the hostile state of Bitocja. Each virus has a specific damage range $d$. When a virus with range $d$ attacks a given server, it disrupts the operation of that server and all other servers that can be reached from it using at most $d$ direct connections.

Bajtazar has an antivirus program at his disposal. Running this program on a given server removes all viruses that have infected it. In particular, this causes these viruses to stop disrupting the operation of the servers they were previously disrupting. Unfortunately, Bajtazar's antivirus program does not protect servers for the future: a server that has been cleaned by Bajtazar will be re-infected in the event of another virus attack.

Your task is to write a library that will help collect security data in the BajtKom network. It will receive information about virus attacks and the execution of antivirus programs, and its task is to report the risk when sending a message between given pairs of servers. The risk is defined as the number of servers on the communication path (including the starting and ending servers) whose operation is disrupted by viruses.

Finally, let us add that the cables connecting the servers in the company are old and easily lose signal strength. For this reason, communication is limited to paths of length at most 500 (this is also the maximum virus damage range and the maximum communication distance).

Interaction

In this task, you should write a C++ library that will communicate with the grader. Your library must provide (implement) the following functions, which will be called by the grader (if you wish, your solution may also contain other functions):

• inicjuj(n) This function will be called only once, at the beginning of the program. Its call informs the library about the number of servers $n$. The servers are numbered from 1 to $n$.

  • C++: void inicjuj(int n);

• polaczenie(a, b) This function will be called $n - 1$ times immediately after the inicjuj function is called. Its call informs the library about the existence of a direct connection between servers numbered $a$ and $b$. You will be informed about the existence of each direct connection exactly once.

  • C++: void polaczenie(int a, int b);

• wirus(a, d) Calling this function informs the library that a virus is infecting server $a$ ($1 \le a \le n$) and starts disrupting the operation of all servers that are at a distance of at most $d$ ($0 \le d \le 500$) direct connections from this server.

  • C++: void wirus(int a, int d);

• antywirus(a) Calling this function informs the library that the antivirus program removes all viruses from server $a$ ($1 \le a \le n$).

  • C++: void antywirus(int a);

• ryzyko(a, b) This function is a library query about the risk of sending a message. Its call should result in the number of servers on the path connecting servers $a$ and $b$ ($1 \le a, b \le n, a \neq b$) whose operation is disrupted by viruses. You can assume that this path consists of at most 500 direct connections.

  • C++: int ryzyko(int a, int b);

Your program must not read any data (neither from standard input nor from files). It also must not write anything to files or standard output. It may write to the standard diagnostic output (stderr) — however, remember that this consumes precious time. Do not declare a main function.

Compilation and Execution

Your sie.cpp library will be compiled with the grader using the command: g++ -O3 -static sie.cpp siegrader.cpp -std=c++17

Examples

The following table presents an example sequence of function calls along with the correct results of the ryzyko function calls. The network structure corresponding to this example is shown in the figure.

Subtasks

Let $q$ denote the total number of calls to wirus, antywirus, and ryzyko. In all subtasks, $1 \le n \le 1\,000\,000$ and $1 \le q \le 100\,000$. Furthermore, as stated earlier, the virus range and the path length between servers in the ryzyko function are no more than 500.