Background

Directly passing a problem by siphoning testdata and “table-based” solutions (hardcoding lookup tables) is cheating; once discovered, you will be brown-named.

This problem does not guarantee that there exists a solution that works for arbitrary data within this problem’s constraints. Because the testdata are weak, a program that passes this problem may be incorrect (e.g., with wrong time complexity or without correctness guarantees). The problem statement and testdata are for reference only. This problem does not accept additional hack testdata.

This is a faulty problem. You are not recommended to attempt or submit to this problem. More details about this type of problem.

Problem Description

Robot Rob can move freely on a tree-shaped path. Given the start $s$ and the end $t$ on the tree $T$, Rob needs to move from $s$ to $t$. There are several movable obstacles on $T$. Because the path is narrow, no two objects can occupy the same position at the same time. In each step, you may move either an obstacle or the robot to an adjacent empty vertex. Design an efficient algorithm to minimize the number of moves needed to move the robot from $s$ to $t$. For the given tree $T$ and the distribution of obstacles in $T$, compute the minimal number of moves for the robot to go from $s$ to $t$.

Input Format

The first line contains three positive integers $n$, $s$ and $t$, denoting the number of vertices of the tree $T$, the index of the start $s$, and the index of the end $t$, respectively.

The next $n$ lines correspond to the vertices of $T$ numbered $0,1,\cdots,n-1$. In each line, the first integer $h$ indicates the initial state of the vertex: when $h = 1$, the vertex is empty; when $h = 0$, the vertex is occupied, containing exactly one obstacle. The second number $k$ indicates that there are $k$ vertices adjacent to this vertex. The following $k$ numbers are the indices of the adjacent vertices.

Output Format

Output the minimal number of moves computed. If the robot cannot be moved from the start to the end, output No solution!.

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

3

Hint

All numbers that appear in the problem are less than $1000$.

Translated by ChatGPT 5