Max Graph Codechef solutions Today | Codechef Starters 72 ✅ (100/100) FULL | AC Code ✅| MAXGRAPH

Problem

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

Sample 1:

3
4
1 0 1 0
5
0 1 2 3 4
3
0 1 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:

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.