8548: Journey
题目描述
NIO and Desprado2 are good friends and they lives in the same city. However, everytime NIO drive to visit desprado2, it takes him a long time to wait for red lights, and NIO is very distressed about this. There are n crossroads in their city. NIO is a very unlucky guy, everytime he go straight, turn left or turn around at a crossroad, he will encounter a red light and have to wait for it. Turning right at a crossroad don't need to wait for the red light.
NIO hates red lights, so he wants to know the minimal number of red lights he would encounter. Can you help him?
输入格式
The first line contains an integer n, 2≤n≤500000, denotes the number of crossroads in the city.
Then follows n lines, each line contains four distinct integers ci,1,ci,2, ci,3,ci,4(0≤ci,j≤n), which denotes the starting points of the four roads to the ith crossroad. If ci,j=0, then this roads are from some other city and NIO will never go this way. The roads are in counter-clockwise order, that is, if NIO are at road <ci,j,i> and wants to go to road <i,ci,j%4+1>, he don't need to wait for the red light because he is turning right at crossroad i, otherwise he will have to wait the red light. It is guaranteed that the map doesn't contain multiple edges and self-loops. It is also guaranteed that all the roads are bi-directional.
The last line contains four integers s1, s2, t1, t2(1≤s1,s2,t1,t2≤n). NIO is at the road <s1,s2> and he wants to go to road <t1,t2> and visit Desprado2. It is guaranteed that both roads are in the map given above.
Please note that road <a,b> is not equivalent to road <b,a>. If NIO is at road <a,b> and he wants to go to road <b,a>, he should turn around at crossroad b and wait for a red light.
输出格式
Output one integer, the minimal number of red lights NIO would encounter.
If there is no way to visit Desprado2, print -1 instead.
输入样例 复制
4
3 4 0 0
0 0 4 3
2 1 0 0
2 0 0 1
4 2 4 1输出样例 复制
1数据范围与提示
One of the optimal route is: turn right at crossroad 2, turn right at crossroad 3, turn right at crossroad 1, and turn around at crossroad 4.
The picture is as follows:
