Shortest Path in a Village Network

You are given a network of villages connected by bidirectional roads. Each road has a weight of 1. Your task is to compute the length of the shortest path from village 1 to village (K). If no such path exists, output -1. The problem requires you to read input from stdin and write the result to stdout.

Formally, given (N) villages, numbered from 1 to (N), and (M) roads connecting pairs of villages, determine the minimum number of roads that must be traversed to reach village (K) from village 1.

inputFormat

The first line contains three integers: (N), (M), and (K), representing the number of villages, the number of roads, and the destination village respectively.

Each of the following (M) lines contains two integers (u) and (v) indicating that there is a bidirectional road between villages (u) and (v).

outputFormat

Output a single integer: the length of the shortest path from village 1 to village (K). If village (K) is unreachable from village 1, output -1.## sample

5 5 4
1 2
2 3
3 4
1 5
5 3

3