Minimum Clicks Between Wiki Pages

Each directed link lets one click jump from u to v; get_links(page) returns the targets of all outgoing edges of that page. Find the minimum number of clicks from start to target; it is 0 if they are the same, and −1 if target is unreachable. Duplicate links and self-loops are allowed.

输入格式

The first line contains m, followed by m lines of u v, and the last line contains start target. 1≤m≤200000, and page names are strings without whitespace. This site's transport protocol adds that a single name has at most 16 Unicode characters (the original 200,000 edges are kept, and the worst-case UTF-8 input is at most 26,000,500 bytes). Names are case-sensitive and need not be pure English.

输出格式

Output the single integer required by the problem.

样例 1

输入：

5
A B
B C
A D
D C
C E
A C

输出：

2

样例 2

输入：

1
A B
B A

输出：

-1

样例 3

输入：

1
A A
A A

输出：

0

样例说明

The answers to the three public examples are, in order: 2; -1; 0. The examples were rechecked by independent enumeration, state search, or direct simulation.