Kinship Distance

Interview

Time limit1sMemory limit128 MB

Summary

Given a family forest of parent-child edges, find the shortest kinship distance between two given people or output -1 if unconnected.

Level: Easy3 of 10
Topics: Graph, BFS, Tree
Solved: No attempts yet

Problem

Family and relative relationships can be represented by a kinship distance. A parent and child have distance 1, and the distance increases by 1 for each parent-child relationship crossed.

Given several parent-child relationships, write a program that computes the kinship distance between two specified people. If the two people are not connected by these relationships, their distance cannot be computed.

Input

People are numbered consecutively from 1 through n (1 <= n <= 100).

The first line contains the total number of people n. The second line contains the numbers of two different people whose kinship distance must be computed. The third line contains m, the number of parent-child relationships.

Each of the next m lines contains two integers x and y, meaning that x is the parent of y.

Each person is given at most one parent.

Output

Print the kinship distance between the two people requested in the input. If the two people are not related through the given relationships, print -1.

Examples2

Example 1
Input
```
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
```
Expected output
```
3
```
Example 2
Input
```
9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
```
Expected output
```
-1
```