#214379. [ROI 2014 Day1] 玩具自动售货机

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

在 E 城的娱乐中心安装了一台新一代的游戏自动机。玩家可以向机器中投入硬币，并观察硬币从上到下穿过一个分叉的管道迷宫。

迷宫中共有 个节点，编号从 到 。每次投入硬币时，硬币会首先进入第 个节点。除第一个节点外，每个节点都恰好有一条从上方通入的管道，硬币可沿着这条管道进入该节点。从每个节点出发，最多有两条向下延伸的管道：一条通向左侧，一条通向右侧。

每条管道都有一定的宽度。当硬币到达某个节点时，它会沿着更宽的管道向下滑落；若两条管道宽度相同，则硬币选择左边的管道。

当硬币通过某条管道后，该管道的宽度会减少 。宽度为 的管道无法再通过硬币。如果硬币到达某个节点，而该节点已无可通行的管道，则机器停止运作，等待下一枚硬币投入。

最初，每个节点中都放有一个玩具。当硬币第一次到达某个节点时，该节点中的玩具会被送给投入该硬币的玩家。

潘克拉特非常喜欢编号为 的节点中的玩具。请编写一个程序，确定潘克拉特最少需要投入多少枚硬币，才能获得节点 中的玩具。

第一行包含一个整数 —— 迷宫中的节点数量。

接下来的 行依次描述所有节点。第 行描述编号为 的节点，包含四个整数 , , , ：

若节点 有一条左管道，则：

• 表示该管道通向的节点编号（满足 ）；
• 表示该管道的初始宽度；

若节点 没有左管道，则 。

同理，若节点 有一条右管道，则：

• 表示该管道通向的节点编号（满足 ）；
• 表示该管道的初始宽度；

若节点 没有右管道，则 。

最后一行包含一个整数 （）—— 潘克拉特想要的玩具所在节点编号。

保证除第一个节点外，每个节点都有且仅有一条进入它的管道。

输出一个整数 —— 潘克拉特需要投入的最少硬币数量，才能获得编号为 的节点中的玩具。如果无法获得该玩具，则输出 。

样例输入 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

样例输出 1

3

样例输入 2

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

样例输出 2

-1

样例解释

在第一个样例中：

• 第一枚硬币经过的路径如下，玩家获得编号为 1、3 和 4 的节点中的玩具：

  :::align{center}

  

  :::

• 第二枚硬币经过的路径如下，玩家获得编号为 2 和 6 的节点中的玩具：

  :::align{center}

  

  :::

• 第三枚硬币经过的路径如下，玩家获得编号为 5 和 7 的节点中的玩具：

  :::align{center}

  

  :::

数据范围

本题包含两个子任务。每个子任务使用独立的测试集进行评测，只有当某个子任务的所有测试通过时，才能获得对应分数。

子任务 1

• 分值：50 分

子任务 2

• 分值：50 分