Toy Vending Machine

Time limit1sMemory limit1024 MB

Summary

Coins travel a tree of tubes, choosing the wider tube (left on ties) and reducing its width by 1; count the coins needed for a coin to first reach node v.

Level: Hard8 of 10
Topics: Tree, Simulation, Greedy, Dynamic programming
Solved: No attempts yet

Problem

An arcade in city E installed a new generation game machine. You can drop a coin into the machine and watch it travel from top to bottom through a branching maze of tubes. The maze has $n$ nodes, numbered from 1 to $n$ . When a coin is dropped, it enters the first node. Every node except the first has exactly one tube entering from above, through which a coin can reach it. Each node has at most two tubes going down, one leading left and the other leading right. Each tube has a width. A coin falls into the wider tube, and if the two tubes have equal width, it falls into the left one.

After a coin passes through a tube, that tube's width decreases by 1. A coin cannot pass through a tube of width 0. If a coin reaches a node from which it cannot move further down, the machine stops and waits for the next coin to be dropped.

Initially, each node of the maze holds one toy. When a coin enters a node for the first time, the toy in that node is taken by the player who dropped that coin.

Pankrat likes the toy in the node numbered $v$ .

Write a program that determines how many coins Pankrat must drop into the machine to get the toy from node $v$ .

Input

The first line contains the number $n$ , the number of nodes in the maze. The next $n$ lines describe all the nodes; the $k$ -th of these lines describes the node numbered $k$ .

The description of node $k$ consists of four integers: $a_k$ , $u_k$ , $b_k$ , $w_k$ . If node $k$ has a left tube, then $a_k$ is the number of the node it leads to ( $k < a_k \leqslant n$ ) and $u_k$ is its width. If there is no left tube, then $a_k = u_k = 0$ . If node $k$ has a right tube, then $b_k$ is the number of the node it leads to ( $k < b_k \leqslant n$ ) and $w_k$ is its width. If there is no right tube, then $b_k = w_k = 0$ .

The last line contains the integer $v$ ( $1 \leqslant v \leqslant n$ ), the number of the node holding the toy Pankrat likes.

Every node except the first has exactly one tube entering it.

Output

Print one number: the number of coins Pankrat must drop into the machine to get the toy in node $v$ . If the chosen toy cannot be obtained, print $-1$ .

Constraints

$1 \le n \leqslant 10^5$
$1 \le u_k, w_k \leqslant 10^9$

Notes

In the first example, the first coin travels the maze along the following path, and the player gets the toys from nodes 1, 3, and 4:

The second coin travels the maze along the following path, and the player gets the toys from nodes 2 and 6:

The third coin travels the maze along the following path, and the player gets the toys from nodes 5 and 7:

Examples2

Example 1

Input

Expected output

Example 2
Input
```
4
0 0 2 1
4 1 3 1
0 0 0 0
0 0 0 0
3
```
Expected output
```
-1
```