机器人路径规划问题

题目背景

**通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。** 本题**不保证**存在**可以通过满足本题数据范围的任意数据**做法。由于测试数据过水,可以通过此题的程序不一定完全正确(算法时间复杂度错误、或不保证正确性)。本题题目和数据仅供参考。本题不接受添加 hack 数据。 本题为错题。**不建议尝试或提交本题。**[关于此类题目的详细内容](https://www.luogu.com.cn/paste/isdgwj5l)

题目描述

机器人 Rob 可在一个树状路径上自由移动。给定树状路径 $T$ 上的起点 $s$ 和终点 $t$,机器人 Rob 要从 $s$ 运动到 $t$。树状路径 $T$ 上有若干可移动的障碍物。由于路径狭窄,任何时刻在路径的任何位置不能同时容纳 $2$ 个物体。每一步可以将障碍物或机器人移到相邻的空顶点上。设计一个有效算法用最少移动次数使机器人从 $s$ 运动到 $t$。对于给定的树 $T$,以及障碍物在树 $T$ 中的分布情况。计算机器人从起点 $s$ 到终点 $t$ 的最少移动次数。

输入输出格式

输入格式


第 $1$ 行有 $3$ 个正整数 $n$,$s$ 和 $t$,分别表示树 $T$ 的顶点数,起点 $s$ 的编号和终点 $t$ 的编号。 接下来的 $n$ 行分别对应于树 $T$ 中编号为 $0,1,\cdots,n-1$ 的顶点。每行的第 $1$ 个整数 $h$ 表示顶点的初始状态,当 $h=1$ 时表示该顶点为空顶点,当 $h=0$ 时表示该顶点为满顶点,其中已有 $1$ 个障碍物。第 $2$ 个数 $k$ 表示有 $k$ 个顶点与该顶点相连。接下来的 $k$ 个数是与该顶点相连的顶点编号。

输出格式


程序运行结束时,将计算出的机器人最少移动次数输出。如果无法将机器人从起点移动到终点,输出 `No solution!`。

输入输出样例

输入样例 #1

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

输出样例 #1

3

说明

题目中出现的数字均小于 $1000$。