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