# Adjacency Hatred | codechef solution

An array is called lovely if the sum of absolute differences of each adjacent pair of elements is odd; formally, the array

$�$ of size $�$ is lovely if ${\sum }_{�=1}^{�-1}$ $\mathrm{\mid }{�}_{�}-{�}_{�+1}\mathrm{\mid }$ is odd.

You are given an array $�$ of $�$ integers. You need to reorder the array in any manner such that the array becomes lovely. If there is no reordering operation that makes the array lovely, output -1.

### Input Format

• The first line contains an integer $�$ denoting the number of test cases. The $�$ test cases then follow.
• The first line of each test case contains an integer $�$.
• The second line of each test case contains $�$ space-separated integers ${�}_{1},{�}_{2},\dots ,{�}_{�}$.

### Output Format

For each test case, print a single line containing $�$ integers denoting the modified array which is lovely, or -1 if it is not possible.

### Constraints

• $1\le �\le 1000$
• $2\le �\le 500$
• $1\le {�}_{�}\le 1{0}^{6}$

### Sample 1:

Input
Output
2
6
3 7 10 1 2 12
2
1 3

1 2 3 10 7 12
-1


### Explanation:

• For the first test case, the sum is $\mathrm{\mid }1-2\mathrm{\mid }+\mathrm{\mid }2-3\mathrm{\mid }+\mathrm{\mid }3-10\mathrm{\mid }+\mathrm{\mid }10-7\mathrm{\mid }+\mathrm{\mid }7-12\mathrm{\mid }=1+1+7+3+5=17$ which is odd.

• For the second test case, $\mathrm{\mid }1-3\mathrm{\mid }=2$ which is even. There is no array that can satisfy the above condition.

Code(C++):-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX INT_MAX
#define MIN INT_MIN
#define mod 1000000007
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vector<int>>
#define endl "\n";
#define pb push_back

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
ll arr[n];
vector<ll>odd,even;
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]%2==0) even.pb(arr[i]);
else odd.pb(arr[i]);
}
int oo=odd.size();
int ee=even.size();
if(oo==0 ||ee==0){
cout<<-1<<endl;
continue;
}
int i=0,j=0;
sort(odd.begin(),odd.end());
sort(even.begin(),even.end());
for(int i:even){
cout<<i<<" ";
}
for(int i:odd)
cout<<i<<" ";

cout<<endl;
}
return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t-->0){
int n = s.nextInt();
int[] a = new int[n];
for(int i = 0;i<n;i++){
a[i] = s.nextInt();
}
int even = 0;
int odd = 0;
for(int i: a){
if((i&1)==0){
even++;
}
else{
odd++;
}
}
if(odd==n||even==n){
System.out.println(-1);
}
else{
int[] ans = new int[n];
int st = 0;
int end = n-1;
for(int i: a){
if((i&1)==0){
ans[end--]=i;
}
else{
ans[st++]=i;
}
}
for(int i: ans){
System.out.print(i+" ");
}
System.out.println();
}
}
}
}