C要--二叉树中的秘密

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

新年伊始,我飞买了一棵二叉树,好有钱啊233

传闻这棵二叉树的某一个节点上隐藏着上古的秘密,于是我飞开始昼夜不息的寻找。本着不遗漏任何一个节点的原则,飞神打算遍历整棵二叉树。
S为飞神当前所处的节点。
S有两个子节点LR,则飞神总是先去遍历节点较少的那棵子树,然后再去遍历另一棵子树,若两棵子树的节点数相等,则飞神会先去遍历编号较小的那棵。

S有一个子节点L,则飞神就去遍历以L为根结点的子树。

S是叶子节点,则飞神会返回到S的父节点。

当飞神遍历完以S为根的子树时就会返回到S的父节点。

当飞神在某个节点发现宝藏时,遍历结束。

开始时,飞神在根结点。

现在给你一棵有n个节点的二叉树T,节点编号从1n,节点1为根结点。

再给你藏有秘密的节点数X,请你计算出我飞需要访问的节点个数,重复访问的只记一次。
 

Input

 多组输入,对于每组输入:

第一行包含一个整数nx(1 <= x <= n <= 3*10^3),分别代表节点个数及藏宝节点编号。

接下来的n行,每行的第一个数为k(0 <= k <= 2),代表第i个节点的子节点个数。

继续读入k个整数,代表第i个节点的k个子节点,详见样例及提示。保证数据合法。

Output

 对于每组数据,输出一个整数代表答案。

Sample Input

5 5
2 2 3
0
2 4 5
0
0
5 1
2 2 3
0
2 4 5
0
0

Sample Output

5
1

Hint

飞神的遍历路线为1->2->1->3->4->3->5

Source

zmx