# -- Answers for the shortest path of the given graphs -- 
# The file consists of a number of test cases.
# Feel free to provide your own test cases!
# Each test case has this structure:
# <number of nodes>
# <space separated SOURCE and DESTINATION node indexes>
# ... <space separated x y coordinates of each node>
# <number of edges>
# ... <space separated nodes edges> (NODE1 is connected to NODE2)
# <distance of the shortest path>
# ...<node ids of the shortest path in the order visited>
# Test case 1:
6
0 5
0 0
2 2
2 -2
4 1
4 -2
6 1
7
0 1
0 2
2 3
1 2
3 5
1 4
0 5
6.082762530298219
0 5
# Test case 2:
4
0 3
0 0
2 0
2 2
4 0
4
0 1
0 2
1 3
2 3
4.0
0 1 3
# Test case 3:
5
0 3
1 3
4 2
-2 4
1 5
-1 4
4
0 1
1 3
4 3
1 4
7.404918347287664
0 1 3