Given an array A of size N, construct a simple (i.e, without self-loops and multiedges) strongly connected directed graph with N nodes where A_{i} denotes the colour of i^{th} node.

The graph should satisfy the following properties:
If A_{i} = A_{j}, then nodes i and j should have the same outdegree.
If A_{i} = A_{j}, neither of the edges i \to j and j \to i should exist.
If the edge u \to v exists, then the edge v \to u cannot exist.
Under the above conditions, the number of edges should be maximized.

Note:
It is guaranteed that A contains at least 2 distinct elements.
If A contains K distinct elements, they will be the integers 0, 1, 2, \ldots, K-1.

Find any graph that satisfies the above conditions.  
If no such graph exists, print -1 instead.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test consists of a single integer N, denoting the number of nodes in the graph.
- The second line contains N space-separated integers A_{1},A_{2},\ldots,A_{N}, where A_{i} denotes the colour of i-th node.

------ Output Format ------ 

For each test case,
- If no valid graph exists, output -1 on a new line.
- Otherwise, first output on a new line M: the maximum number of edges in such a graph.
- Then, output M lines, each containing two space-separated integers u and v, denoting an edge from u to v.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$0 ≤ A_{i} < K$, where $K$ is the number of distinct elements in $A$.
- The sum of $N$ over all test cases won't exceed $1000$.

----- Sample Input 1 ------ 
3
4
1 0 1 0
5
0 1 2 3 4
3
0 1 1
----- Sample Output 1 ------ 
4
1 2
3 4
4 1
2 3
10
1 2
2 3
2 4
2 5
3 1
3 4
3 5
4 1
4 5
5 1
-1
----- explanation 1 ------ 
Test case $1$: Nodes $1$ and $3$ are colored $1$, and nodes $2$ and $4$ are colored $0$.    
The out degree of nodes $[1,3]$ is $1$ and out degree of nodes $[2,4]$ is also $1$, and the graph is strongly connected.

Test case $2$: Every node has a distinct color, so those conditions are automatically satisfied. $10$ edges is also the maximum possible number of edges such a graph can have.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Constructive algorithms


Solutions:
import math

def solve_for(a, b, c):
	if b == 0:
		assert a == 1
		return (c, 0)
	else:
		(v, u) = solve_for(b, a % b, c)
		v -= a // b * u
		q = u // b
		u -= b * q
		v += a * q
		return (u, v)
for _ in range(int(input())):
	n = int(input())
	cs = [int(x) for x in input().split()]
	assert len(cs) == n and n >= 1
	n_cs = max(cs) + 1
	c_ct = [cs.count(c) for c in range(n_cs)]
	assert n_cs >= 1 and sum(c_ct) == n and all((x > 0 for x in c_ct))
	if n_cs == 1:
		print(0 if n == 1 else -1)
		continue
	if n_cs >= 3:
		print(sum((x * y for (i, x) in enumerate(c_ct) for y in c_ct[:i])))
		for j in range(n):
			for i in range(n):
				if cs[i] < cs[j] and (cs[i] != 0 or cs[j] != n_cs - 1) or (cs[i] == n_cs - 1 and cs[j] == 0):
					print(i + 1, j + 1)
		continue
	a = c_ct[0]
	b = c_ct[1]
	as_ = [i for i in range(n) if cs[i] == 0]
	bs_ = [i for i in range(n) if cs[i] == 1]
	g = math.gcd(a, b)
	if g > 1:
		print(a * b)
		for i in range(0, a, g):
			for j in range(0, b, g):
				for k in range(0, g):
					print(as_[i + k] + 1, bs_[j + k] + 1)
					for l in range(g):
						if k != l:
							print(bs_[j + l] + 1, as_[i + k] + 1)
	elif a <= 2 or b <= 2:
		print(-1)
	else:
		delta = 2 if max(a, b) % min(a, b) == 1 else 1
		m = a * b - delta
		print(m)
		(u, v) = solve_for(a, b, m)
		assert u >= 0 and v >= 0 and (u * a + v * b == m)
		for i in range(u * a):
			print(as_[i % a] + 1, bs_[i % b] + 1)
		for j in range((a - v) * b, a * b):
			print(bs_[j % b] + 1, as_[j % a] + 1)