Adjacency Love ~ WildLife-TK

An array is called lovely if the sum of product of each adjacent pair of elements is odd.

More formally, the array $S$

of size

M

is lovely if the value

\sum_{i = 1}^{M - 1}

(S_{i} . S_{i + 1})

is odd.

You are given an array $A$

consisting of

N

positive integers. Find a permutation of array

A

which is lovely.

If multiple such permutations are possible, output any. If there is no lovely permutation, output -1.

denoting the number of test cases. The

T

test cases then follow.

The first line of each test case contains an integer

N

The second line of each test case contains

N

space-separated integers

A_{1}, A_{2}, \dots, A_{N}

For each test case, if a lovely permutation of $A$

is possible, print a single line containing

N

integers denoting the elements of any lovely permutation of

A

. Otherwise, print -1.

2 \leq N \leq 500

1 \leq A_{i} \leq 10^{6}

3 1 10 2 4
-1

Test Case $1$

: The sum of products of adjacent pair of elements of the given array is

1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 10 = 2 + 6 + 12 + 40 = 60

. Since this value is even, this is not a lovely permutation of the array.
A lovely permutation of the given array is

[3, 1, 10, 2, 4]

. The sum of products for this array would be

3 \cdot 1 + 1 \cdot 10 + 10 \cdot 2 + 2 \cdot 4 = 41

, which is odd.

Test Case $2$

: No permutation of the given array exists where the sum of products of adjacent pair of elements is odd. Thus, answer is

- 1