Background

LAR got fired by the boss, and everything below is his dream.

Problem Description

There are $n$ companies in the city. The $i$-th company has $m_i$ people.

A company can be represented by a tree rooted at $1$. Initially, node $1$ is the boss. The children of a node are its subordinates, and the parent of a node is its supervisor. The size of the $i$-th tree is $m_i$, with nodes numbered from $1$ to $m_i$.

There are too many companies, and it is troublesome for the government to manage them, so the government wants LAR to merge these companies. To merge two companies, one person in one company who initially has no subordinates (an employee or the boss) becomes the supervisor of the current boss of the other company. After the merge is completed, the two companies become one company.

Only two people who are supervisor and subordinate of each other know each other.

myz is node $x$ in the $1$-st tree, and ljs is node $y$ in the $2$-nd tree. Because myz and ljs have very incompatible personalities (they do not know each other), LAR wants their relationship to be as far as possible.

The distance between two people who know each other is $1$. The relationship between two people is defined as the shortest distance between them in the social network (you can simply treat it as the shortest distance between the two nodes in the final tree). For example, if $1$ knows $2$ and $2$ knows $3$, then the relationship between $1$ and $3$ is $2$.

Input Format

The first line contains an integer $n$, representing the number of companies.

Lines $2$ to $n+1$: in line $i+1$, the first integer is $m_i$, representing the number of people in the $i$-th company. Then there are $m_i - 1$ integers; the $j$-th number represents the supervisor of node $j+1$ in this tree.

Line $n+2$ contains two integers $x$ and $y$, meaning myz is node $x$ in the $1$-st tree, and ljs is node $y$ in the $2$-nd tree.

Output Format

Output one integer, representing the maximum possible relationship value between myz and ljs.

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

8

Hint

Sample Explanation

Before any merge operations, the companies in the city are as follows (the number in parentheses is the company where the node belongs initially):

To maximize the relationship value, the final company can be formed as shown below:

The answer is $8$.

Constraints

This problem uses bundled testdata.

Random tree generation rule: for node $i$ ($2 \le i \le m$), its supervisor is chosen uniformly at random from $1$ to $i - 1$.

For $100\%$ of the testdata, $2 \leq n \leq 10^5$, $1 \le m_i$, $\sum m \leq 10^6$, $1 \leq x \leq m_1$, $1 \leq y \leq m_2$.

Translated by ChatGPT 5