P10406 「SMOI-R1」Company

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

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$.

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 one integer, representing the maximum possible relationship value between myz and ljs.

### 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**. subtask ID|$n\leq$|$\sum m \leq$|Special case|Score -|-|-|-|- $1$|$2$|$10^3$|None|$20$ $2$|$10^5$|$10^6$|$x = 1$, $y = 1$|$20$ $3$|$10^5$|$10^6$|All trees are random trees|$20$ $4$|$10^5$|$10^6$|None|$40$ **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