A marshalling yard is a place where train carriages are connected or disconnected to maintain and repair trains. There are tracks in the yard where trains can move. We will represent the positions of train carriages on the tracks as a graph. Each edge in the graph represents a state where one carriage of the train is located, and thus the train is represented as a path on the graph. In this case, all vertices and edges on the path must be distinct. Specifically, the graph given in the problem is always a tree.

Trains can be moved along the tracks. The movement of a train occurs in steps, and in one step, one end carriage of the train moves to an adjacent edge. Specifically, for a path $P$ representing a train, the result of a one-step movement is a path obtained by adding an edge and a vertex adjacent to one end vertex of $P$ that is outside $P$, and removing the edge and vertex at the other end of $P$ (Figure 1). Note that the length of the path does not change at each step.

Figure 1

Given are two paths $P$ and $Q$ of length $m$, representing the initial and final positions of the train, respectively. The length of a path is the number of edges included in the path. Here, the two paths $P$ and $Q$ do not share any edges. In other words, there is no edge that $P$ and $Q$ traverse at the same time. We must move path $P$ so that it eventually becomes path $Q$. At this time, we must find the minimum number of steps.

Given a tree $T$ with $n$ vertices and two paths $P$ and $Q$ of length $m$ representing the initial and final train positions, write a program that checks if $P$ can be moved to $Q$ and, if it can, outputs the minimum number of steps.

For example, in Figure 2, two paths $P$ and $Q$ of length 2 that do not share any edges are given. As shown in the figure, it is possible to move from path $P$ to $Q$ in 5 steps, and this is the minimum number of steps.

Figure 2

You must implement the following two functions for the administrator.

• void init(int n, vector<int> X, vector<int> Y): This function is called initially and only once. The number of vertices in the tree is $n$, and the vertices are represented by integers from 1 to $n$. $X$ and $Y$ are vectors of size $n-1$, and each edge of the tree is represented as $(X[i], Y[i])$.
• long long train(vector<int> Z): $Z$ is a vector of size 4 representing the two endpoints $Z[0]$ and $Z[1]$ of the initial path $P$, and the two endpoints $Z[2]$ and $Z[3]$ of the final path $Q$. Return the minimum number of steps to move $P$ to $Q$. If it is impossible to move, return -1.

Implementation Details

You must submit exactly one file named train.cpp. This file must implement the following two functions:

• void init(int n, vector<int> X, vector<int> Y)
• long long train(vector<int> Z)

These functions must operate as described above. Of course, you may create other functions to use internally. The submitted code must not perform input/output or access other files.

Examples

Input 1

11 2
1 2
3 2
4 3
4 5
6 5
8 4
7 8
8 9
10 9
11 10
3 5 7 4
3 6 7 10

Output 1

3
7

Note

The following sequence of function calls is performed for Example 1: 1. init(11, {1, 3, 4, 4, 6, 8, 7, 8, 10, 11}, {2, 2, 3, 5, 5, 4, 8, 9, 9, 10}) 2. train({3, 5, 7, 4}) returns 3 3. train({3, 6, 7, 10}) returns 7