Fencepost Relay

# Fencepost Relay ## Problem Farmer John wants to set up a relay race between cows using fenceposts as stations. There are $N$ fenceposts arranged across the field, numbered $1$ to $N$. Between pairs of fenceposts, there are $M$ undirected paths that cows can run along to relay messages. Your task is to find the minimum number of hops (paths) a message must travel to get from fencepost 1 (the start) to fencepost $N$ (the finish). If there is no path connecting post 1 to post $N$, output $-1$. ## Input The first line contains two integers $N$ and $M$ ($1 \le N \le 1000$, $0 \le M \le 5000$). The next $M$ lines each contain two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$), indicating a path between fencepost $u$ and fencepost $v$. ## Output Output a single integer: the minimum number of hops from post 1 to post $N$, or $-1$ if no such path exists. ## Constraints - $1 \le N \le 1000$ - $0 \le M \le 5000$ - There are no duplicate edges - The graph is undirected ## Sample Input ``` 5 5 1 2 2 3 1 4 4 5 3 5 ``` ## Sample Output ``` 2 ``` ## Explanation The fenceposts form a network where: - Post 1 connects to posts 2 and 4 - Post 2 connects to posts 1 and 3 - Post 3 connects to posts 2 and 5 - Post 4 connects to posts 1 and 5 - Post 5 connects to posts 4 and 3 The shortest path from post 1 to post 5 is: $1 \to 4 \to 5$, which takes 2 hops.