Metro

The plan of the metro consists of $n$ stations located on $l$ lines. Each station belongs to one or more lines (in this case it is possible to pass in one station from one line to another). Each line consists of two or more stations and intersects with at least one other line. The plan of the metro is connected.

The movement between two nearby stations of one line can be done in any direction during $2$ min. The transferring from one line to another in one station can be done in $1$ min. It is possible to neglect any other waste of time.

You have to find the minimum time necessary for the manager of the company "Diez-product" to get from station $a$ to the apartment of office of company, that is located near station $b$.

Input

Two positive integers $n$ and $l(1\le l\le 10)$ are given in the first line. Each of the next $l$ lines contains the successive numbers of the stations of one metro line. The last line contains the number and line of the initial and final stations. All integers are positive and do not exceed $70$.

Output

Print the minimum travel time between the given stations.

Examples