The 2018 World Cup was held recently in Russia. Some great soccer countries (e.g., Italy, Netherlands, Chile, USA) did not qualify for this World Cup. These countries have found out that they needed more effective passing.
Given the player positions for two teams, determine the minimum number of passes needed to get the ball from one player to another player. For the purposes of this problem, players do not change position, i.e., they do not move.
Player P1 can pass the ball directly to P2 if they are on the same team and no other player is in between the two players.
The first input line contains an integer, n (2 ≤ n ≤ 11), indicating the number of players on each team. The second input line contains 2n integers, providing the (x,y) coordinates for the n players on Team 1; the first integer on this input line is the x coordinate for Player 1, the second integer is the y coordinate for Player 1, the third integer is the x coordinate for Player 2, etc. The third input line provides (in a similar fashion) the (x,y) coordinates for the n players on Team 2. Assume that all coordinates are integers between 1 and 999 (inclusive) and that all players are on distinct locations, i.e., no two players occupy the same spot (point).
Assume Player 1 on Team 1 has the ball and wants to pass the ball to Player n on Team 1. Assume that any player can pass the ball any distance.
The output consists of a single integer, indicating the minimum number of passes needed to get the ball from Player 1 on Team 1 to Player n on Team 1. If it is not possible to get the ball from Player 1 to Player n, print -1.
10 15 13 17 10 19
10 17 16 17 13 19
1 1 3 1 5 1 7 1 9 1
2 1 4 1 6 1 8 1 10 1
1 1 5 5 2 2
10 10 50 50 20 20