Maximizing Interpersonal Distance in Merged Companies

There are \( n \) companies in the city. The \( i\)-th company has \( m_i \) employees. Each company is represented by a rooted tree whose nodes are numbered \( 1, 2, \dots, m_i \) and whose root \(1\) is the boss. In the tree, every child is a subordinate of its parent.

To merge two companies, the rule is that one company selects a person who originally had no subordinate (this could be an employee or even the boss if it is the only person in the company) and makes that person a subordinate of the current boss of the other company. After each merge, the two companies become one. Note that in the resulting organization, only those who are in a direct superior–subordinate relationship know each other.

You are given two special persons: myz is node \( x \) in the first company and ljs is node \( y \) in the second company. Since they do not know each other, LAR wants to maximize the relationship distance between them.

The relationship distance between two people is defined as the length of the shortest path between them in the final merged tree, where two people who directly know each other have a distance of \(1\). For example, if \(1\) knows \(2\) and \(2\) knows \(3\), then the distance between \(1\) and \(3\) is \(2\).

You may control the order in which the companies are merged. When merging companies, note that the only freedom is to choose, in the donating company, which originally leaf (a node with no subordinate in its original tree) will be used to attach the other company’s boss. In an optimal merge order, the unique path between myz and ljs in the final tree will include:

• a path in the first company from myz to a chosen originally leaf,
• a merge edge connecting that leaf to the boss of another company,
• possibly several intermediate companies where, for each, you can add the maximum distance from its boss (node \(1\)) to some originally leaf plus the merge edge connecting it to the next company, and
• a final portion from the boss of the second company (node \(1\)) down to ljs.

If we define:

• \( d_1 \): the maximum distance in tree 1 from node \( x \) (myz) to any originally leaf in company 1,
• \( d_2 \): the distance from the boss of company 2 (node \(1\)) to node \( y \) (ljs) in tree 2, and
• For every other company (i.e. companies 3 through \( n \)), let \( h_i \) be the maximum distance from its boss (node \(1\)) to any originally leaf,

then by using all companies in the chain the maximum possible distance is

\[ \text{Answer} = d_1 + d_2 + (n-1) + \sum_{i=3}^{n} h_i. \]</p>

Your task is to compute and output this maximum relationship distance.

inputFormat

The input begins with an integer \( n \) (\( n \ge 2 \)) representing the number of companies.

Then, for each company \( i \) from \(1\) to \( n \):

• A line with an integer \( m_i \) indicating the number of employees.
• If \( m_i > 1 \), the next line contains \( m_i - 1 \) integers. The \( j \)-th integer (for \( j = 2, 3, \dots, m_i \)) is the parent of node \( j \) in that company’s tree.

The final line contains two integers \( x \) and \( y \), meaning that myz is node \( x \) in the first company and ljs is node \( y \) in the second company.

outputFormat

Output a single integer representing the maximum possible relationship distance between myz and ljs after optimally merging all companies.

sample

2
3
1 1
2
1
2 2

4