题目描述

译自 ROI 2014 Day1 T1. Автомат с игрушками

在 E 城的娱乐中心安装了一台新一代的游戏机。玩家可以向机器投掷硬币，并观察硬币从顶部到底部穿过一个分叉的管道迷宫。迷宫中有 $n$ 个节点，编号从 $1$ 到 $n$。当硬币被投入时，它会首先进入编号为 $1$ 的节点。除了第一个节点外，每个节点都有一个从上方进入的管道，硬币可以通过该管道到达该节点。每个节点最多有两条向下延伸的管道，一条通向左下方，另一条通向右下方。每条管道都有一定的宽度。硬币会优先掉入宽度较大的管道，如果两条管道宽度相等，则会选择左侧的管道。

硬币通过一条管道后，该管道的宽度会减少 $1$。如果管道宽度为 $0$，硬币将无法通过。如果硬币到达一个无法继续向下移动的节点，机器会停止运行，等待下一枚硬币的投入。

初始时，迷宫的每个节点内都放置了一件玩具。当硬币第一次到达某个节点时，该节点内的玩具将被投掷硬币的玩家获得。

潘克拉特看中了编号为 $v$ 的节点内的玩具。

你需要编写一个程序，计算潘克拉特需要投掷多少枚硬币，才能获得编号为 $v$ 的节点内的玩具。

输入格式

输入文件的第一行包含一个整数 $n$，表示迷宫中节点的数量。

接下来的 $n$ 行描述了各个节点的情况，第 $k$ 行描述编号为 $k$ 的节点。

编号为 $k$ 的节点的描述包含四个整数：$a_k, u_k, b_k, w_k$。

• 如果编号为 $k$ 的节点有通向左下方的管道，则 $a_k$ $(k < a_k \leq n)$ 表示该管道通向的节点编号，$u_k$ 表示该管道的宽度；如果没有左管道，则 $a_k = u_k = 0$。
• 如果编号为 $k$ 的节点有通向右下方的管道，则 $b_k$ $(k < b_k \leq n)$ 表示该管道通向的节点编号，$w_k$ 表示该管道的宽度；如果没有右管道，则 $b_k = w_k = 0$。

输入文件的最后一行包含一个整数 $v$ $(1 \leq v \leq n)$，表示潘克拉特看中的玩具所在的节点编号。

保证除了第一个节点外，所有节点都只有一条从上方进入的管道。

输出格式

输出文件应包含一个整数，表示潘克拉特需要投掷的硬币数量，以获得编号为 $v$ 的节点内的玩具。如果无法获得该玩具，则输出 $-1$。

7
2 1 3 2
0 0 6 3
4 1 5 1
0 0 0 0
7 2 0 0
0 0 0 0
0 0 0 0
5

3

在第一个样例中，第一枚硬币将沿以下路径穿过迷宫，玩家将获得编号为 $1$、$3$ 和 $4$ 的节点中的玩具。

第二枚硬币将沿以下路径穿过迷宫，玩家将获得编号为 $2$ 和 $6$ 的节点中的玩具。

第三枚硬币将沿以下路径穿过迷宫，玩家将获得编号为 $5$ 和 $7$ 的节点中的玩具。

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

-1

数据范围与提示

详细子任务附加限制及分值如下表所示：