All Submissions


In computer networks, routing of packets from source to destination in minimum time is one of the main concerns. For this purpose routers interchange their routing tables from time to time and thus create a picture of network. When a packet is recieved, the router computes the optimal path that packet must take and then forward it to next router. Now I want to simulate the process. For this I considered only number of hops (routers) for optimal path, i.e. the path containting minimum number of hops between source and destination is considered as the optimal path.

There will be T testcases. In each testcase, N routing tables will be given each of L lines. Each line in a routing table will have 2 integers, A and B, implying that there is direct link between A and B. On the last line of each test case there will be two integers, S and D, which are source and destination respectively. Your job is to print the number of hops in optimal path from S to D. If destination is not reachable then print -1.

Note : We have updated the constrains. Sorry for inconvenience



Input

3

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

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

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


Output

-1
2
2


Constraints
1 <= T <= 100
1 <= N <= 10
1 <= L <= 25
A, B, S, D is any integer (Both +ve and -ve integers)

Problem Setter : Pushkar Anand

Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0