Advanced Persistent Threat

You have just discovered that the server network you supervise is the victim of a cyberattack. A group of hackers managed to infiltrate and remain hidden for a long period of time. They started from one server and spread by moving through the links between servers across the entire network. Now you must discover the initial server from which the intruders connected and stop their connection.

The network consists of servers and links between these servers represented by cables. A link allows two servers to communicate with each other. Also, there is at most one link between two distinct servers and no link between a server and itself. You have the option to check a link and see whether it was used in the attack, and if it was used, you will also learn the direction of malware propagation. You do not want to allow those hackers to stay long in the network, so you want to find the computer from which the attack started as quickly as possible.

Task

You must implement a function

int Find (int n, vector <int> a, vector <int> b)

The parameters are: $n$, which represents the number of servers; $a$ and $b$, which are two vectors representing the computers between which there exists a link (there exists a link between $a_i$ and $b_i$). This function must return the index of the server from which the attack started.

Your function will communicate with the grader function:

int Ask (int x, int y)

This allows you to find out whether the link between $x$ and $y$ was used in the attack or not. If the link does not exist or was not used in the attack, the function will return the value $0$. Otherwise, if $y$ was infected through $x$, then the function will return the value $1$. If server $x$ was infected through $y$, then the function will return $-1$.

To work, your program must include "apt.h".

To make local testing easier, you are provided in the problem sources with an example grader and solution, and the file apt.h.

Constraints

Let $N$ be the number of servers and $M$ the number of links. Then,

• $1 \le N \le 1\,000$
• $N - 1 \le M \le 2 \cdot N$
• Servers are indexed starting from $1$
• Any server is connected to at most $4$ other servers
• It is guaranteed that for any two servers in the network there exists at least one communication path through the existing links
• All servers were infected exactly once
• The network was generated randomly such that if we considered only the links used to infect the servers, then the maximum distance between two servers would be $O(n)$. The other links were added randomly.

Scoring

Your program will run on multiple tests. If you do not return the correct answer or your program encounters a compilation error, time limit exceeded, memory limit exceeded, or any other error, then you will receive $0$ points on that test. Otherwise, your score will be given based on the number of calls to the function "Ask".

The total score will be distributed over multiple subtasks, and the score obtained on a subtask will be the minimum score obtained on any of the tests in that subtask. The final score will be the sum of the scores over all subtasks.

For each test, your number of calls, denoted $Q$, will be compared with the number of calls to the function "Ask" in the committee solution, denoted $Q_{comisie}$. Also, $D$ is defined as $\lfloor\frac{M + Q_{comisie}}{2}\rfloor$. On a test you will receive points based on the following formula, where $P$ represents the score of the subtask to which the test belongs:

$Punctaj\ primit = \begin{cases} P,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dacă\ Q < Q_{committee}\\ P \cdot (1 - \sqrt\frac{Q - Q_{committee} + 1}{D - Q_{committee} + 1}),\ dacă\ Q_{committee} \le Q \le D\\ 0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ dacă\ Q > D \end{cases}$

The terms $Q_{committee}$ were taken from a deterministic solution to which a certain indulgence term was added.

Example

The example grader will read the number of servers, the number of links, and then, on each line, the links in the network. On each line describing a link there will be $3$ numbers, the first two being the servers between which there is a link, and the next number will be $-1$ if the first computer was infected through the second, $0$ if the link was not used in the network, and $1$ if the second server was infected through the first. At the end, it will print the answer returned by your program and the number of calls to the function “Ask”.

stdin

6 8
3 1 1
2 1 -1
1 6 1
3 5 1
4 5 -1
6 4 0
2 4 0
3 4 0

stdout

3 4

Explanation

The network in the example consists of $6$ servers and $8$ links. The hackers started their attack from server $3$. From server $3$ they spread to servers $1$ and $5$. From server $1$ they spread to servers $2$ and $6$, and from server $5$ they spread to server $4$. All servers were infected exactly once.
One way to obtain the correct answer in $4$ questions is to call the function “Ask” as follows: $Ask(4, 5)$, $Ask(3, 1)$, $Ask(3, 4)$, $Ask(3, 5)$. The answers will be, in this order: $-1$, $1$, $0$, $1$. After these $4$ questions we can be sure that the server from which the attack started is server number $3$, so we return $3$.