A new toy machine has been installed in the game shop Damian patronises.
You can throw a coin into the machine and watch it roll downwards from the top of the machine.
There are N containers in the machine, numbered from 1 to N. The container numbered 1 is at the top of the machine. The containers are connected using tubes. Each container, other than the container numbered 1, is connected by one tube at the top of the container, as well as at most 2 tubes at the bottom of the container, one leading to the left and the other to the right. Coins can enter a container from the tube at the top and exit the container from the tube at the bottom (if any).
Each tube has a diameter. When a coin is in a container, it will fall into the tube with the larger diameter, and if the container is connected by two tubes of equal width, the coin will fall into the tube on the left. After a coin passes through a tube, its diameter decreases by 1. A coin cannot pass through a tube with a diameter of 0. If a coin cannot fall further down when it is in a container, it stays in the container, the machine stops and waits for Damian to insert another coin. Each container can contain an unlimited number of coins.
There is a toy in each container. The toy in a container is dispensed by the machine the first time a coin passes through it. Damian wants the toy in the container numbered V.
What is the minimum number of coins Damian must throw to obtain the desired toy?
The first line of input contains N, the number of containers in the machine.
The following N lines contain descriptions of each of the N containers.
The Kth line contains four integers AK, UK, BK, WK, the description of container K.
AK represents the container the left tube leads to, and UK represents the diameter of the left tube. If there is no left tube, AK = UK = 0.
BK represents the container the right tube leads to, and WK represents the diameter of the right tube. If there is no right tube, BK = WK = 0.
It is guaranteed that each container, except the container numbered 1, is connected to exactly 1 tube at the top.
The last line of input contains a single integer V, the number of the container with the toy that Damian desires.
Output a single integer, the minimum number of coins Damian needs to throw to get his desired toy.
If Damian cannot get his desired toy, output -1.
For all subtasks, K < AK, BK ≤ N for each K. 1 ≤ V ≤ N.
Subtask 1 (50%): 1 ≤ N ≤ 100. 1 ≤ UK, WK ≤ 300.
Subtask 2 (50%): 1 ≤ N ≤ 100 000. 1 ≤ UK, WK ≤ 109.
Subtask 3 (0%): Sample Testcases
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
The first coin will pass through the containers shown below. Containers 1, 3 and 4 will dispense toys.
The second coin will pass through the containers shown below. Containers 2 and 6 will dispense toys.
The third coin will pass through the containers shown below. Containers 5 and 7 will dispense toys.
As Damian has obtained the toy from container 5, there is no need for him to continue throwing coins.
4 0 0 2 1 4 1 3 1 0 0 0 0 0 0 0 0 3