This is an interactive problem.

Description

You are a treasure hunter who has heard that a vast amount of mysterious treasure is hidden within the Treasure Holding University (THU). You decide to go and investigate.

You have gathered some information about the university online: there are $n$ landmarks and $m$ bidirectional roads connecting these landmarks, such that any two landmarks are reachable from each other. The treasure is buried beneath one of these landmarks.

You have contacted a senior student at the university who knows the exact location of the treasure, but he cannot tell you directly—that would be leaking university secrets. However, you managed to extract some useful information from him:

1. The roads at the university are carefully designed such that if you start from any landmark, travel along any path, and return to the starting landmark, the number of roads traversed is always even. It is said that this helps alleviate bicycle congestion on campus.

2. The administrative area where the school is located has been upgraded to medium-risk due to confirmed cases, and the school regulations prohibit anyone who has passed through medium- or high-risk areas within 14 days from entering. Therefore, you must skydive into the campus. Since you have a helicopter, you do not intend to explore every landmark along the roads; instead, you can choose any landmark to land on and jump between landmarks at will.

3. Before you enter the campus, the senior can leave some hints for you: he will place an arrow on every road in the school, pointing to one of the two landmarks connected by that edge. However, once you arrive on campus, you can no longer contact the senior and must rely on yourself.

4. All landmarks in the school are unlabeled, which may increase the difficulty of your treasure hunt.

Unfortunately, you do not have a map of the university, and you do not even know the number of roads $m$; you only know the number of landmarks $n$. Of course, the senior knows all the information.

Before attracting the attention of school officials, you have limited time to visit a number of distinct landmarks, and you can only choose one landmark to excavate for the treasure. Whether you succeed depends on the cooperation between you and the senior.

Implementation Details

You do not need to, and should not, implement the main function. You only need to implement the following two functions:

void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[]);

int Bob(const int testid, const int n);

The Alice function represents the senior's hints. Here, $testid$ is the subtask number, $n$ is the number of landmarks, $m$ is the number of roads, and $x$ is the index of the landmark where the treasure is buried. The arrays $u$ and $v$ both have size $m$ and describe the roads on campus; the $i$-th road connects landmarks $u[i]$ and $v[i]$. (All indices and labels are 0-based, same below.)

The Alice function needs to write the output into the dir array, which has size $m$, representing the direction of the arrow for each edge. $dir[i]=0$ means the arrow of the $i$-th edge points to $v[i]$, and $dir[i]=1$ means it points to $u[i]$.

The Bob function represents your treasure hunting process. $testid$ and $n$ have the same meanings as above. This function needs to return the index of the landmark where you choose to excavate.

During the execution of the Bob function, you can call the following function:

vector<pair<int,bool>> discover(int pos);

This function represents visiting the landmark with index $pos$, where $0 \leq pos < n$ must be satisfied. By visiting, you can obtain information about all edges connected to this point, stored in a vector. Each edge's information is represented by a pair<int,bool>, where the first element is the index of the other landmark the edge points to, and the second element is the direction of the arrow on this edge (0 means it points to the other landmark, 1 means it points to the current landmark). Additionally, within the same test case, you cannot visit the same landmark more than once.

In a single test case, the Alice function will be executed once, followed by the Bob function. To reflect the unlabeled nature of the landmarks, after the Alice function finishes, all landmark indices will be randomly shuffled. All landmark indices involved in the Bob function, including the $pos$ passed to discover, the landmark indices returned by discover, and the return value of Bob, refer to the shuffled indices. Furthermore, the order of edges returned by discover is not the same as the order passed to Alice, but is given in a random order. (In some test cases, the landmark indices will not be randomly shuffled; see "Constraints" for details.)

Additionally, you may define other variables or functions as needed. However, any changes made to global variables in the Alice function will not be reflected in the Bob function.

Your Alice function can only access the $0 \sim m-1$ indices of arrays $u$ and $v$ and cannot modify them. It can only access and modify the $0 \sim m-1$ positions of the dir array; out-of-bounds access may cause unexpected errors.

Your program must include the following header file:

#include "treasure.h"

Examples

Input 1

1 3 2 0
0 1
1 2

Output 1

Correct.
cnt = 1

Note

The following is an implementation of encoding and decoding that is not guaranteed to be correct but might pass this example. You can refer to this implementation to familiarize yourself with the use of the interaction library.

void Alice(const int testid, const int n, const int m, const int x, const int u[], const int v[], bool dir[])
{
    dir[0] = true;
    for(int i = 1; i < m; ++i)
        dir[i] = false;
}

int Bob(const int testid, const int n)
{
    vector<pair<int,bool>> e = discover(0); 
    return 0;
}

When the landmark indices are not randomly shuffled, this program can pass this example, and the information in $e$ returned by discover(0) is as follows: $e.size()$ is $1$, $e[0].first$ is $1$, and $e[0].second$ is $true$.

Subtasks

There are 25 subtasks in total, each worth 4 points, consisting of multiple test cases.

For each test case, if your program does not terminate normally, or the return value of the Bob function is incorrect (i.e., not the re-labeled treasure location), or you call the discover function more than $5 \times 10^5$ times, or the calls to discover do not meet the requirements, or there is any other violation, you will receive 0 points. Otherwise, your score will be determined by the number of times $cnt$ you call the discover function:

$cnt \leq 5000$: 4 points;

$5000 < cnt \leq 10^4$: 3 points;

$10^4 < cnt \leq 5 \times 10^4$: 2 points;

$5 \times 10^4 < cnt \leq 5 \times 10^5$: 1 point;

$cnt > 5 \times 10^5$: 0 points.

Your score for each subtask is the minimum score among all test cases in that subtask.

Constraints

For all test cases, it is guaranteed that $2 \leq n \leq 10^6$, $n-1 \leq m \leq 2 \times 10^6$, $0 \leq u[i], v[i], x < n$. The provided map is a connected graph with no self-loops or multiple edges, and every cycle has an even length.