3

# Ninja Port

Difficulty: HARD
Contributed By
Nishant Chitkara

Problem Statement
Suggest Edit

#### Since the underground paths are secret and having too many paths in the same colony could lead the Ninja community getting caught, there are at most ‘P’ underground paths in each colony (which includes incoming and outgoing underground paths).

##### Note:
``````The secret underground paths cannot be used to travel both ways, you can’t travel from destination to source.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains four space-separated integers, ‘N’, ‘K’, ‘S’ and ‘P’ denoting the number of colonies, number of houses in each colony, the number of secret underground paths and the maximum number of underground paths in a colony respectively.

The next line contains four space-separated integers “sourceHouse”, “sourceColony”, “destinationHouse” and “destinationColony” denoting the house number and colony number of Ninja’s initial position and house number and colony number of the destination house respectively.

The next ‘S’ line contains four space-separated integers each denoting the arrays “secretPaths[i]”.
``````
##### Output Format :
``````For each test case, return an integer denoting the minimum time Ninja takes.

Output for each test case will be printed in a new line.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given functions.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 100
1 <= K <= 10^9
1 <= P <= 50
0 <= S <= (P * N) / 2

Where ‘T’ denotes the number of test cases,
‘N’ denotes the number of colonies,
‘K’ denotes the number of houses in each colony,
‘P’ denotes the maximum number of underground paths in a colony and
‘S’ denotes the number of underground paths.

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````1
5 5 1 1
3 1 3 5
1 1 5 5
``````
##### Sample Output 1:
``````3
``````

#### Explanation For Sample Output 1:

``````The path Ninja follows would be (colony number, house number) = (1, 3) -> (1, 1) -> (5, 5) -> (5, 3).

The first teleport from (1, 3) -> (1, 1) can be performed as both of the houses are in the first colony.

The next transition (1, 1) -> (5, 5) can be done using the underground path and the last one from (5, 5) -> (5, 3) can be done as both the houses are in the fifth colony.
``````
##### Sample Input 2 :
``````2
10 5 2 2
2 3 4 10
1 1 5 10
5 8 4 7
7 8 0 0
8 4 6 7
``````
##### Sample Output 2 :
``````7
6
``````
Console