Key Item Recovery (Problem K, CS3233 Midterm Contest 2024, 2024)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
Pichuu, the Pokemon Master, faced a dilemma after destroying Team Galactic, becoming the champion and catching every legendary Pokemon. He realized he had lost his town map, a precious item given to him by his mother and also a Key Item! To avoid her scolding, Pichuu decided to reconstruct the map.

The town map was originally a bidirectional connected graph with $N$ towns, each labeled distinctly from 1 to $N$, where there was exactly one path between any two towns. Pichuu, unfortunately, forgot the direct connections between towns. While distraught, he discovered a useful feature on his trusty Poketch – it recorded the paths he took.

However, for each path from town $i$ to town $j$, the Poketch only recorded the town with the minimum label on the path, $A_{i,j}$. (The Poketch Company is still working out the bugs). For example, if the path on the map was $4 \to 2 \to 3 \to 5$, the Poketch will record 2 for the path from 4 to 5.

Working with what he got, Pichuu tries to reconstruct a fake Town Map that satisfies the records made by the Poketch. Pichuu however is a Pokemon Master, not a Graph Master. Please help him recover his town map.

Namely, construct a tree that satisfies the condition that the minimum label on the path from town $i$ to $j$ is $A_{i,j}$.

# Constraints

- $1 \leq N \leq 1500$.
- $1 \leq A_{i,j} \leq N$

# Input

The first line contains a single integer, $N$, the number of towns.  
$N$ lines follows, the $i^{th}$ line contains $N$ space-separated integers, $A_{i,1}, A_{i,2}, \dots A_{i,N}$ where $A_{i,j}$ is the town with the smallest label on the path from town $i$ to $j$.  
It is guaranteed there exists a solution given the provided values.

# Output

Output $N-1$ lines, each with two space-separated integers $A_i B_i$ representing an edge in your reconstructed town map.

# Sample Input #1
```
3
1 1 1 
1 2 1 
1 1 3 
```
# Sample Output #1
```
2 1
3 1
```
# Sample Input #2
```
6
1 1 1 1 1 1 
1 2 2 2 2 2 
1 2 3 2 2 2 
1 2 2 4 2 2 
1 2 2 2 5 2 
1 2 2 2 2 6 
```
# Sample Output #2
```
2 3
2 4
2 5
2 6
1 2
```

Sample inputs:
3
1 1 1 
1 2 1 
1 1 3

6
1 1 1 1 1 1 
1 2 2 2 2 2 
1 2 3 2 2 2 
1 2 2 4 2 2 
1 2 2 2 5 2 
1 2 2 2 2 6

Sample outputs:
2 1
3 1

2 3
2 4
2 5
2 6
1 2

# Solution Analysis

Let’s remove node 1 from the tree. This will split the tree into $1 \leq K$ subtrees.

Note that if $A_{i,j} > 1$ then nodes $i$ and $j$ are in the same subtree. Since nodes in different subtree will have to pass through town 1 in the original tree and having a minimum node of 1. Now we have a way of identifying if two nodes are in the same subtree.

Thus we can the set of nodes of each subtree, by simply iterating through the nodes, and then checking against a node in each subtree set. If it belongs to a subtree set, add it to the set, else if it does not belong to any set then create a new subtree set.

Note that we can then abitrarily choose a node from each subtree set, let this be $T_i$ for $i^{th}$ subtree, and add edge from that node to 1. This is valid as for $x, y$, if $x$ and $y$ belong in the same subtree, they will not use this edge to 1, thus they are not affected by what $T_i$ is. If $x$ and $y$ are in different subtree ($i$ and $j$), then their path will involve $x \rightarrow T_i \rightarrow 1 \rightarrow T_j \rightarrow y$. Thus regardless of what $T_i$ and $T_j$ is, it does not affect the result that $A_{x,y} = 1$.

Hence, we can construct the edges of node 1. We can then do this recursively on the smallest node in each subtree and eventually construct the entire graph.

Note that the time complexity of this recursively algorithm is $O(N^2)$. Proof is left as an exercise to the reader. Hint: Consider a subtree to be represented as an edge and how many times is that subtree set being compared against.


Special judge (C++ scorer):