Determining a Valid Meeting Point

DerrickLo controls a city in a game. The city has n towns (numbered from 1 to n), each hosting exactly one group. The towns are connected by n-1 bidirectional paths so that any two towns are reachable, i.e. the graph is a tree. When a meeting is held, groups whose town numbers lie in a given interval [l, r] are invited.

However, the groups are so inflexible that when an invited group travels from its home town to the meeting town p, it must not pass by any other town hosting an invited group – that is, in the unique simple path from the group’s town to p, none of the intermediate towns (i.e. excluding the starting town and p) may belong to the invited set S = \{l, l+1, \dots, r\}.

Your task is to choose a meeting town p (an integer from 1 to n) satisfying the condition. In particular, for every invited town i (with i \in S and i ≠ p), if we denote by \(\mathit{path}(i, p)\) the unique simple path from i to p, then none of the vertices in \(\mathit{path}(i, p)\) excluding the endpoints should belong to S.

If no valid meeting point exists, output -1.

inputFormat

The first line contains an integer n (\(2 \le n \le 2000\)) representing the number of towns.

The next n-1 lines each contain two integers u and v (\(1 \le u, v \le n\)) indicating a bidirectional path between town u and town v.

The last line contains two integers l and r (\(1 \le l \le r \le n\)), defining the interval of invited groups.

outputFormat

Output a single integer p (\(1 \le p \le n\)) that represents a valid meeting town such that for every invited town i \in \{l, l+1, \dots, r\}\) with i ≠ p, the unique simple path from i to p does not contain any other invited town in between. If no such town exists, output -1.

sample

3
1 2
1 3
1 3

1