Anna is a resident of the IOI Islands and has decided to invite her friend Bruno to visit. The IOI Islands consist of $N$ islands, numbered from 1 to $N$. There are $N-1$ bridges, numbered from 0 to $N-2$. Bridge $i$ connects island $A_i$ and island $B_i$ bidirectionally. It is possible to travel between any two islands using the bridges. Anna's house is on island $T$, but Bruno does not know the number of the island where Anna's house is located.

To help Bruno, Anna decides to place one flag with an integer written on it on each of the $N$ islands. Anna does not know the number of the island where Bruno will arrive.

Bruno arrives at island $S$ by boat. Upon arriving at island $S$, Bruno is given the following information: The number of the island he arrived at, $S$, and the integer written on the flag placed on island $S$. The numbers of all islands directly connected to island $S$ by a bridge, and the integers written on the flags placed on those islands.

When traveling from island $S$ to island $T$, Bruno must take the path with the minimum number of bridges.

Can Bruno, based solely on the information given to him, determine whether the island $S$ he arrived at is the island $T$ where Anna's house is located, and if $S$ and $T$ are different, correctly choose the next island to head towards?

Task

Given the information about the IOI Islands, write a program that implements Anna's strategy of placing flags with integers. Also, write a program that implements Bruno's strategy of correctly choosing the next action based on the information given when he arrives at an island.

Implementation Details

You must submit two files in the same programming language.

The first file is named Anna.c or Anna.cpp. This file implements Anna's strategy and must implement the following routine:

• void Anna(int K, int N, int T, int A[], int B[])

This routine is called exactly once at the beginning. The argument K is the subtask number $K$. The argument N is the number of islands $N$ in the IOI Islands. The argument T is the number of the island $T$ where Anna's house is located. The arguments A and B are arrays of length $N-1$. The elements A[i] and B[i] indicate that bridge $i$ connects island A[i] and B[i] ($0 \le i \le N-2$).

Additionally, you must call the following routine to place flags on the islands:

• void Flag(int I, int V)

• The argument I represents the number of the island where Anna places the flag.

• The argument V represents the integer Anna writes on the flag.

However, calls to Flag must satisfy the following: I must be an integer between 1 and $N$ inclusive. If this is not satisfied, it results in a Wrong Answer [1]. Flag must not be called more than once with the same argument I. If this is not satisfied, it results in a Wrong Answer [2]. V must be an integer between 0 and $N$ inclusive. If this is not satisfied, it results in a Wrong Answer [3]. Flag must be called exactly $N$ times. If this is not satisfied, it results in a Wrong Answer [4].

If a call to Flag is determined to be incorrect, the program execution is terminated at that point.

The second file is named Bruno.c or Bruno.cpp. This file implements Bruno's strategy and must implement the following routine:

• void Bruno(int K, int S, int F, int L, int P[], int Q[])

This routine is called exactly once after Anna has been called. The argument K is the subtask number $K$. The argument S represents the number of the island $S$ where Bruno arrived. The argument F represents the integer written on the flag placed on island $S$. The argument L is the number of islands $L$ directly connected to island $S$ by a bridge. The argument P is an array of length $L$ containing the numbers of the islands directly connected to island $S$ by a bridge. The argument Q is an array of length $L$ where the element Q[j] represents the number written on the flag placed on island P[j] ($0 \le j \le L-1$).

Additionally, you must call the following routine to determine whether Anna's house is on the island $S$ where Bruno arrived, and if not, correctly choose the next island to head towards:

• void Answer(int X)

• The argument X is the number of the island $T$ where Anna's house is located if it is on the island Bruno arrived at. Otherwise, it is the number of the island Bruno should head to next.

However, calls to Answer must satisfy the following: The argument X must be one of the elements of array P, or S. If this is not satisfied, it results in a Wrong Answer [5]. If Answer is called more than once, it results in a Wrong Answer [6]. If Answer is not called, it results in a Wrong Answer [7]. If Anna's house is on island $S$ and the argument X is not $T$, it results in a Wrong Answer [8]. * If Anna's house is not on island $S$ and the argument X is not the next island to head towards, it results in a Wrong Answer [9].

After the Bruno routine is called, the answer is judged.

You are free to implement other routines for internal use or declare global variables. However, since the two submitted programs are linked together with the grading program into a single executable file, you must declare all global variables and internal routines in each file as static to avoid interference with other files. During grading, this program is executed as two separate processes, one for the Anna side and one for the Bruno side, so global variables cannot be shared between the Anna side and the Bruno side.

Your submission must not communicate with standard input/output or any other files in any way.

Constraints

All input data satisfies the following conditions: $2 \le N \le 100\,000$. $1 \le S \le N$. $1 \le T \le N$. $1 \le A_i \le N$ ($0 \le i \le N-2$). $1 \le B_i \le N$ ($0 \le i \le N-2$). $1 \le K \le 4$. * It is possible to travel between any two islands in the IOI Islands using the bridges.

Subtasks

Subtask 1 [10 points]

• $K = 1$ is satisfied.

Subtask 2 [15 points]

• $K = 2$ is satisfied.
• The value of the argument V passed to Flag must be between 0 and 2 inclusive.

Subtask 3 [20 points]

• $K = 3$ is satisfied.
• The value of the argument V passed to Flag must be 0 or 1.
• No island is directly connected to exactly two islands by bridges.
• $S \neq T$ is satisfied.

Subtask 4 [55 points]

• $K = 4$ is satisfied.
• The value of the argument V passed to Flag must be 0 or 1.

Examples

Input 1

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

Output 1

Accepted : V_max = 1

Note

In this example, the calls to Flag are not necessarily meaningful. In this case, the arguments passed to Anna(...) and Bruno(...) are as follows: