「SMOI-R1」Company

题目背景

LAR 被老板炒了,下面都是他的梦。

题目描述

城市中有 $n$ 所公司,第 $i$ 所公司有 $m_i$ 个人。 一所公司可以用一棵**根为 $1$ 的**树来表示,**最初时**节点 $1$ 是老板,每个节点的子节点都是他的下属,每个节点的父节点都是他的上司。第 $i$ 棵树的大小为 $m_i$,节点从 $1$ 到 $m_i$ 编号。 公司很多,政府管理起来非常麻烦,所以政府想让 LAR 把这些公司合并起来。两所公司要合并起来,需要**一所**公司的一名**最初没有下属**的人(员工或**老板**)成为**另一所**公司现在的**老板的上司**。当两个公司合并完,两所公司就是**一所公司**了。 只有**互为上司和下属**的两个人才认识。 myz 是第 $1$ 棵树的节点 $x$,ljs 是第 $2$ 棵树的节点 $y$。因为 myz 和 ljs 性格十分不相符(他们不认识),所以 LAR 想让他们的**关系越远越好**。 互相认识的人距离为 $1$,**两人的关系**定义为两人的人际关系网上的最短距离(可以简单认为是最终形成的树中两点的最短距离)。例如,$1$ 认识 $2$,$2$ 认识 $3$,那么 $1$ 和 $3$ 的关系就是 $2$。

输入输出格式

输入格式


第一行有一个整数 $n$,代表公司数量。 第二行到第 $n+1$ 行中,第 $i + 1$ 行第一个整数是 $m_i$,代表第 $i$ 所公司的人的数量。接下来有 $m_i - 1$ 个整数,第 $j$ 个数代表这棵树中节点 $j+1$ 的上司。 第 $n+2$ 行有两个整数 $x$ 和 $y$,代表 myz 是第 $1$ 棵树的节点 $x$,ljs 是第 $2$ 棵树的节点 $y$。

输出格式


输出一个整数,代表 myz 和 ljs 关系的最大值。

输入输出样例

输入样例 #1

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

输出样例 #1

8

说明

### 样例解释 在还没有进行合并操作时,城市中公司如下(括号中的数是节点**初始时**所在的公司): ![](https://cdn.luogu.com.cn/upload/image_hosting/1g1uvci4.png) 想要让关系值最大,可以让最终的公司形成下图的样子: ![](https://cdn.luogu.com.cn/upload/image_hosting/cj518ep6.png) 答案为 $8$。 ### 数据范围 **本题采用捆绑测试**。 subtask编号|$n\leq$|$\sum m \leq$|特殊情况|分值 -|-|-|-|- $1$|$2$|$10^3$|无|$20$ $2$|$10^5$|$10^6$|$x = 1$,$y=1$|$20$ $3$|$10^5$|$10^6$|所有树都是随机树|$20$ $4$|$10^5$|$10^6$|无|$40$ **随机树产生规则**:对于节点 $i$ ($2 \le i \le m$)的上司从 $1$ 到 $i - 1$ 中**等概率**产生。 对于 $100\%$ 的数据,$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$。