Specialist Programmer

Ninja and his friend are playing a game. They are having ‘N’ piles and each pile contains ‘A[i]’ amount of stones in it. Ninja will make the first move.

In each move, a player can choose any pile and remove any number of stones ( at least one ) from that pile. The player who cannot make a move loses the game.

Assuming both players play optimally, output 1 if Ninja wins the game and 0 if Ninja loses the game.

Example :

N = 3
A = [ 3, 4, 5 ]

Explanation : 

One of the optimal ways to play the game is : 

Ninja removes 3 stones from the first pile : [ 0, 4, 5 ].
Friend removes 3 stones from the second pile : [ 0, 1, 5 ].
Ninja removes 3 stones from the third pile : [ 0, 1, 1 ].
Friend removes 1 stone from the second pile : [ 0, 0, 1 ].
Ninja removes 1 stones from the third pile : [ 0, 0, 0 ].

Thus Ninja wins the game here.

Ninja has built his team of ninjas to fight with the enemies in his city. Ninja made a plan of attacking all his enemies. In his team, every ninja has his own range of hitting and they had secretly got the hitting range of their enemies as well. So Ninja allowed some swaps between his ninjas so that they can minimize the hamming distance that is the number of positions where the hitting range of enemies and ninjas are different.

Your task is to write a code that can minimize the hamming distance. You are being provided with two arrays ‘ninja’ and ‘enemies’ both of the same size and an array ‘allowedSwaps’ where each allowedSwaps[i] = [ ai, bi ] indicates that you are allowed to swap the elements at index ai and index bi.

The Hamming distance of two arrays of the same length, ninja, and enemies, is the number of positions where the elements are different.

Example :

Consider the case ‘ninja’array is [ 1, 2, 3, 4 ], ‘enemies’array is [ 2, 1, 4, 5 ] and ‘allowedSwaps’ are  = [ [ 0, 1 ], [ 2, 3 ] ] so after swapping in best manner according to ‘allowedSwaps’ our ‘ninja’ array becomes [ 2, 1, 4, 3 ]. So minimum Hamming distance is ‘1’ as now there is only one different element as compared to ‘ninja’ and ‘enemies’ array index.

Note :

1. You are allowed to do as many swap operations on the ‘ninja’ array as you want but according to the ‘allowedSwap’ array.
2. You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

The city of Ninjaland is analogous to the unweighted graph. The city has ‘N’ houses numbered from 1 to ‘N’ respectively and are connected by M bidirectional roads. If a road is connecting two houses ‘X’ and ‘Y’ which means you can go from ‘X’ to ‘Y’ or ‘Y’ to ‘X’. It is guaranteed that you can reach any house from any other house via some combination of roads. Two houses are directly connected by at max one road.

A path between house ‘S’ to house ‘T’ is defined as a sequence of vertices from ‘S’ to ‘T’. Where starting house is ‘S’ and the ending house is ‘T’ and there is a road connecting two consecutive houses. Basically, the path looks like this: (S , h1 , h2 , h3 , ... T). you have to find the shortest path from ‘S’ to ‘T’.

For example

In the below map of Ninjaland let say you want to go from S=1 to T=8, the shortest path is (1, 3, 8). You can also go from S=1 to T=8  via (1, 2, 5, 8)  or (1, 4, 6, 7, 8) but these paths are not shortest.