Teleportation Across Nations

There are \( n \) countries numbered from \(0\) to \(n-1\). In the \(i\)-th country, there are \( m_i \) cities (numbered from \(0\) to \(m_i-1\)), with city \(0\) being its capital. The cities of each country are connected by roads forming a tree rooted at the capital. Note that the roads allow free travel within the country (i.e. moving along a road takes \(0\) time).

Only the leaf cities in each country are equipped with a teleportation portal. A teleportation portal can transfer you from a leaf city in one country to any leaf city in an adjacent country (i.e. a country with an index differing by exactly \(1\) from the current country) and takes \(1\) unit of time. Important: Each portal can be used only once. That is, if a portal is used for teleportation (either as the departure portal or the destination portal), it cannot be used again.

You are given a starting city \((s_{c}, s_{x})\) and a target city \((t_{c}, t_{x})\). Within each country you may travel by roads freely (and instantly) between any cities, but you can only teleport from a leaf city to a leaf city in a neighboring country. If you are not initially in a leaf city and you wish to teleport, you may first travel (for free) by roads to any leaf city in the same country. However, in doing so, you must make sure that different teleportations in the same country use different leaf cities; for an intermediate country along your journey (one that is used as both the destination of one teleportation and the departure for the next), you must have at least two distinct leaves available.

Your task is to determine the minimum total time required to go from the starting city to the target city. If the start and target are in the same country, no teleportation is needed and the answer is \(0\). Otherwise, let \(a = s_{c}\) and \(b = t_{c}\) (assume \(a \le b\); if not, swap them). Then the journey requires teleportation from country \(a\) to \(a+1\), \(a+1\) to \(a+2\), …, up to country \(b\). In doing so:

• Country \(a\) must have at least one leaf city (to serve as the departure portal).
• Country \(b\) must have at least one leaf city (to serve as the arrival portal).
• Every intermediate country (with index \(i\) where \(a < i < b\)) must have at least two distinct leaf cities (one for arrival and one, different, for departure).

If these conditions cannot be satisfied, output \(-1\). Otherwise, the minimum time is \(|t_{c} - s_{c}|\) (since each teleport uses 1 unit time and road travel is free).

Note: The tree of each country is given as an undirected graph; however, treat city \(0\) as the root to determine which cities are leaves (a leaf is defined as a node with no children in the tree rooted at \(0\); thus, the capital is a leaf if and only if the country has only one city).

inputFormat

The input begins with an integer \(n\) \( (1 \le n \le 100)\) representing the number of countries.

For each country \(i\) from \(0\) to \(n-1\):

1. A line with an integer \(m_i\) \( (1 \le m_i \le 10^5)\) indicating the number of cities in that country.
2. Then \(m_i - 1\) lines follow, each containing two integers \(u\) and \(v\) \((0 \le u,v < m_i)\) describing an undirected road connecting city \(u\) and city \(v\). It is guaranteed that these roads form a tree.

Finally, there is a line containing four integers: s_c s_x t_c t_x, where \(s_c\) and \(s_x\) denote the country and city of the starting location, and \(t_c\) and \(t_x\) denote the country and city of the target location.

You may assume that the total number of cities over all countries does not exceed \(10^5\) and that all cities are numbered starting from \(0\) with city \(0\) being the capital in each country.

outputFormat

Output a single integer representing the minimum time required to travel from the start city to the target city. If it is impossible to complete the journey under the given conditions, output \(-1\).

sample

1
3
0 1
1 2
0 0 0 2

0