# Palindrome Swaps Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

Palindrome Swaps Codechef Solution

## Problem

Chef has N strings. Each string S_i has length M and consists only of lowercase english letters.

Chef likes palindromes, and would like each S_i to be a palindrome. To achieve this, he can perform the following move:

• Pick an index i such that 1 \leq i \lt N and an index j such that 1 \leq j \leq M.
• Then, swap the j^{th} character of string S_i with the j^{th} character of string S_{i+1}.

Informally, Chef can swap the j^{th} character of any two consecutive strings.

Find the minimum number of moves required to make every string a palindrome. Print -1 if it is not possible to achieve this.

### Input Format

• The first line of input contains a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains two space-separated integers N and M, denoting the number of strings and their length, respectively.
• The i^{th} of the next N lines contains the string S_i.

### Output Format

• Print a single integer on a new line as the answer to each test case: the minimum number of swaps needed to make every S_i a palindrome, or -1 if this is not possible.

### Constraints

• 1 \leq T \leq 5\cdot 10^5
• 1 \leq N, M \leq 5 \cdot 10^5
• Each S_i contains only lowercase english letters.
• The sum of N\times M across all test cases won’t exceed 5\cdot 10^5.

### Sample 1:

Input

Output

4
3 2
ac
ba
cb
2 3
xkx
ptp
4 4
abaa
baba
baab
aabb
4 4
abaa
baba
baab
aaab

2
0
-1
3


### Explanation:

Test case 1: Chef can make all the strings palindromes in two operations:

• First, swap the second characters of S_1 and S_2. Now, the strings are \{\texttt{aa, bc, cb}\}
• Then, swap the first characters of S_2 and S_3. Now, the strings are \{\texttt{aa, bb, cc} \}, which are all palindromes.

Test case 2: Both strings are already palindromes.

Test case 3: It can be shown that it’s impossible to make all 4 strings simultaneously palindromes.

Test case 4: One optimal sequence of operations is as follows:

• Swap the first characters of S_3 and S_4. Now, the strings are \{\texttt{abaa, baba, aaab, baab} \}.
• Swap the second characters of S_1 and S_2. Now, the strings are \{\texttt{aaaa, bbba, aaab, baab} \}.
• Swap the fourth characters of S_2 and S_3. Now, the strings are \{\texttt{aaaa, bbbb, aaaa, baab} \}.

Thus, the final strings are all palindromes. It can be proven that we cannot achieve all palindromes in less than 3 moves.

## Palindrome Swaps Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW