Minimum Clicks Between Wiki Pages

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Minimum Clicks Between Wiki Pages with Link Fetch Simulator

You have a set of wiki pages where each page may link to other pages. You must implement a link fetch simulator and then compute the minimum number of clicks needed to navigate from start to target (one click follows one outgoing link).

Tasks

Implement get_links(page): return the list of pages directly reachable from page.

Using get_links, compute the minimum clicks from start to target:

If start == target, the answer is 0

If target is unreachable, return -1

Input (for this simulator-based problem)

Line 1: integer m, number of directed links

Next m lines: two strings u v meaning a link from u to v

Last line: two strings start target

get_links(page) should behave as: return all x such that an input edge page -> x exists.

Output

One line: the minimum click count, or -1

Constraints

1 <= m <= 2*10^5

Page names are whitespace-free strings

Sample Tests (5)

Input:

5

A B

B C

A D

D C

C E

A C

Output:

2

Input:

3

A B

B C

C D

A D

Output:

3

Input:

2

A B

C D

A D

Output:

-1

Input:

1

A A

Output:

0

Input:

4

A B

A C

B D

C D

A D

Output:

2

Example

Input

5

A B

B C

A D

D C

C E

A C

Output

2

Complete solveMinimumWikiClicks. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.