# Most Lucky String

#### Mr. X is planning to visit Ninja Land. Ninja Land has 'N' cities numbered from 0 to 'N-1' and 'M' bidirectional roads. Each road connects two of the 'N' cities, and no two cities have multiple roads between them. All the 'N' cities have a certain 3 letter code given in the array 'ARR'. Mr. X will stay at Ninja land for exactly 'K' days, and he does not like to stay in the same city for two consecutive days. Therefore, he needs to change his city every day of his stay. He also has a special string that is initially empty. Mr. X has a habit that whenever he visits a city, he appends the code of that city to his special string.

#### Mr. X has a lucky string 'S' of length '3*K'. Mr. X wants to plan his stay in such a manner that the number of places where the final special string differs from the lucky string is the minimum possible. Your task is to find any such order of cities that Mr. X should visit satisfying the above conditions.

##### Input Format :

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains three space-separated integers, 'N', 'M' and 'K', denoting the number of cities, the number of bidirectional roads, and the number of cities that Mr. X will visit, respectively.
The second line of each test case contains 'N' space-separated strings denoting the elements of the array 'ARR'.
The third line of each test contains the special string 'S'.
The next 'M' lines of each test case contain the description of the 'M' roads.
The 'i'th' line contains two space-separated integers, 'City1', 'City2'. 'City1' and 'City2' denote the two cities that are connected by the 'i'th' road.
```

##### Output Format :

```
For each test case, the checker will print "valid" if the returned order of cities results in a string that differs from the lucky string 'S' at the minimum possible places. Otherwise, the checker will print "invalid".
Print the output of each test case in a new line.
```

##### Note :

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints :

```
1 <= T <= 10
2 <= N <= 1000
1 <= M <= min(1000,(N*(N-1))/2)
1 <= K <= 100
|ARR[i]| = 3
|S| = 3*K
0 <= City1, City2 <= N-1
Every city is reachable from every other city, any two cities are directly connected by at most one road and all the input strings contain uppercase English letters only.
Where 'T' denotes the number of test cases, 'N' denotes the number of cities, 'M' denotes the number of roads, 'K' denotes the number of cities that Mr. X will visit, ARR[i] denotes the 'i'th' element of the array 'ARR', 'S' denotes the lucky string, 'City1' and 'City2' denotes the two cities that are connected by the 'i'th' road, .
Time Limit : 1 sec
```

The idea is to use a recursive approach to generate all the possible orders of cities that Mr. X should visit and select the best path. The recursive idea is very clear that if Mr. X visits any city on the **i'th** day, then he can go to any of the cities connected to that city on the **(i+1)**'**th **day. Using this idea, we can generate all the possible order of cities Mr. X can visit. After generating the corresponding special string for a particular path, we will count the number of places the generated string differs with the lucky string. In the end, we will select the path for which the generated string differs with the lucky string at the least possible places.

**Steps: **

- Let
**adj**be the adjacency list of the given graph. - Let
**minDifference**be a variable that stores the minimum number of places the generated string differs with the lucky string. Initialize it as**INT_MAX.** - Let
**ans**be an array of size**K**that stores the path that Mr. X should follow. - We will define a function
**generateOrders(i, j, currentDifference, currentOrder)**to generate all orders if we go through City**i**on the**j'th**day**.**The variable**currentDifference**stores the number of places the current path differs, and**currentOrder**stores the order of cities in the current path.- Iterate from
**l = 0**to**2**- If
**arr[i][l]**is not equal to**S[3*j+l]**, then increase**currentDifference**by 1.

- If
- Add the index
**i**to the array**currentOrder.** - If
**j**equals**K - 1**, then- If
**currentDifference**is smaller than**minDifference,**then set**currentDifference**as min difference, and update**ans**as**currentOrder.**

- If
- Otherwise
- Iterate through the adjacency list of city -
**i**- Let
**neighbour**be the current city. - Call the function
**generateOrders(neighbour, j+1, currentDifference, currentOrder).**

- Let

- Iterate through the adjacency list of city -

- Iterate from
- Iterate from
**i = 0**to**N - 1**- Initialize
**currentDifference**as 0, and**currentOrder**as an empty array. - Call
**generateOrders(i, 0, currentDifference, currentOrder).**

- Initialize
- Return the array
**ans.**

In the previous approach, the function **generateOrder(i, j, currentDifference, currentOrder) **is recursively being calculated several times for the same values. So, here we can use the technique of memoization to optimize the working of the previous approach. We will create a 2D Matrix to store all the previously computed values so that no value is being calculated multiple times.

**Steps: **

- Let
**adj**be the adjacency list of the given graph. - We will define two 2-D arrays having
**N**and**K**columns. The first array,**minChanges,**will be used to store the number of changes from the lucky string,**minChanges[i][j]**stores the minimum possible changes from the special string possible if we visit**i'th**city on the**j'th**day. Note that we are storing all the changes done from the**j'th**day to the final day. Initialize all its elements as**INT_MAX.**The second array,**optimalOrder,**stores the city that should be visited on the next day, which we will use to generate the best path after finding the minimum difference possible that can be achieved. Initialize all its elements as -1. - We will define a function
**findMinDifference(i, j)**to find the minimum number of differences we can get if we visit the City -**i**on**j'th**day**.**- If
**minChanges[i][j]**is not equal to**INT_MAX,**then we will return**minChanges[i][j]**as we have already calculated it. - Set the variable
**currentChanges**as 0. - Iterate from
**l = 0**to 2- If
**ARR[i][l]**is not equal to**S[3*j + l]**, then increase**currentChanges**by 1.

- If
- If
**j**equals**K - 1**then, we will return**currentChanges.**This serves as the base case of the recursive function. - Otherwise,
- Iterate through the adjacency list of the city -
**i**- Let
**neighbour**be the current city. - Call the function
**findMinDifference(neighbour, j+1).**Let**currDifference**be the returned value. - If
**currDifference + currentChanges**is smaller than**minChanges[i][j]**, then- Set
**minChanges[i][j]**as**currDifference + currentChanges.** **Update optimalOrder[i][j] as neighbour.**

- Set

- Let
- Return
**minChanges[i][j].**

- Iterate through the adjacency list of the city -

- If
- Initialize
**start**as -1 and**minTotalChanges**as**INT_MAX.** - Iterate from
**i = 0**to**N - 1**- Call
**findMinDifference(i, 0).**Let**currTotalChanges**be the returned value. - If
**currTotalChanges**is smaller than**minTotalChanges,**then- Set
**minTotalChanges**as**currTotalChanges.** - Set
**start**as**i.**

- Set

- Call
- Let
**ans**be the array of size**K**that stores the order in which Mr. X should visit cities. - Let
**dayCount**be a variable to store the count of the current day. Initialize it as**0.** - While
**dayCount**is less than**K**, then- Set
**ans[dayCount]**as**start**. - Set
**start**as**optimalOrder[start][dayCount].** - Increase
**dayCount**by 1.

- Set
- Return the array
**ans**

In the first approach, the function **generateOrder **recursively generates all the possible paths, which has many overlapping subproblems. i.e. a recursive function computes the same sub-problems again and again. So we can use Dynamic Programming to overcome the overlapping subproblems.

**Steps:**

- We will define two 2-D arrays having
**N**and**K**columns. The first array,**minDifference,**will be used to store the DP states,**minDifference[i][j]**stores the minimum possible difference from the special string possible if we visit**i'th**city on the**j'th**day. Initialize all its elements as**INT_MAX.**The second array,**optimalOrder,**stores the city that should be visited on the previous day, which we will use to generate the best path after finding the minimum difference possible that can be achieved. Initialize all its elements as -1. - Iterate from
**i = 0**to**N - 1**- Set
**minDifference[i][0]**as 0. - Iterate from
**l = 0**to 2- If
**ARR[i][l]**is not equal to**S[l]**, then increase**minDifference[i][0]**by 1.

- If

- Set
- Iterate from
**i = 1 to K - 1**- Iterate through the edge list,
- Let
**firstCity**and**secondCity**be the two cities connected by the current edge. - Set the two variables
**firstCost**and**secondCost**as 0 each. - Iterate from
**l = 0**to 2- If
**ARR[firstCity][l]**is not equal to**S[3*i + l]**, then increase**firstCost**by 1. - If
**ARR[secondCity][l]**is not equal to**S[3*i + l]**, then increase**secondCost**by 1.

- If
- If
**minDifference[firstCity][i]**is greater than**minDifference[secondCity][i-1] + firstCost,**then- Set
**minDifference[firstCity][i]**as**minDifference[secondCity][i-1] + firstCost.** - Update
**optimalOrder[firstCity][i]**as**secondCity.**

- Set
- If
**minDifference[secondCity][i]**is greater than**minDifference[firstCity][i-1] + secondCost,**then- Set
**minDifference[secondCity][i]**as**minDifference[firstCity][i-1] + secondCost.** **Update optimalOrder[secondCity][i] as firstCity.**

- Set

- Let

- Iterate through the edge list,
- Let
**start**be the index of the row having the minimum value in the last column in the array**minDifference**. This is the index of the city that Mr. X should end his journey. - Let
**ans**be the array of size**K**that stores the order in which Mr. X should visit cities. - Let
**dayCount**be a variable to store the count of the current day. Initialize it as**K - 1.** - While
**dayCount**is greater than equal to 0, then- Set
**ans[dayCount]**as**start**. - Set
**start**as**optimalOrder[start][dayCount].** - Decrease
**dayCount**by 1.

- Set
- Return the array
**ans.**