Maximum Chemical Yield

You are given a series of chemical reactions. Each reaction is represented as a one‐step conversion in the form $A \rightarrow B$, with a conversion rate $C$ ($0<C<1$). This indicates that starting with 1 unit of compound $A$, the reaction produces $C$ units of compound $B$. You are also given two compounds $S$ and $T$. Starting from $1$ unit of compound $S$, your task is to determine the maximum amount of compound $T$ that can be produced by choosing an appropriate sequence of reactions.

Note: If it is impossible to produce compound $T$ starting from $S$, output 0.

Hint: Since the yield of a series of reactions is the product of the individual conversion rates, this problem can be solved using a variant of the Bellman-Ford algorithm to maximize the product along a path.

inputFormat

The first line contains a single integer N ($1 \le N \le 10^4$), the number of reactions.

Each of the next N lines contains two strings A and B and a floating point number C ($0<C<1$), representing a reaction that transforms compound A to compound B with conversion rate C.

The last line contains two strings S and T, the starting and target compounds respectively.

outputFormat

Output a single floating point number: the maximum amount of compound T that can be produced starting from 1 unit of S. If T cannot be reached from S, output 0.

sample

3
A B 0.5
B C 0.7
A C 0.4
A C

0.35