You are a courier navigating a region of N towns, labeled 0 to N-1. You are given a list of bidirectional highways connecting these towns. Your goal is to find the minimum number of highways you need to travel to deliver a package from your starting town S to your destination town D.
If it is completely impossible to reach the destination from the starting town, return -1.
The first line contains an integer T, representing the number of test cases.
For each test case:
The first line contains four space-separated integers: N (number of towns), M (number of highways), S (starting town), and D (destination town).
The next M lines each contain two space-separated integers u and v, indicating a bidirectional highway between town u and town v.
For each test case, print a single integer: the minimum number of highways needed to reach D from S. Print -1 if no route exists.
| Example Input | Example Output |
|---|---|
3 5 4 0 4 0 1 1 2 2 4 0 3 4 2 0 3 0 1 2 3 3 3 0 2 0 1 1 2 0 2 |
3 -1 1 |