IZLET

Nikola has recorded an N×N matrix from his observation of a tree with N nodes. Each node is assigned a color from 1 to N. The value in the i^th row and j^th column of the matrix equals the number of distinct colors that appear on the unique simple path from node i to node j in the tree.

Your task is to reconstruct any tree along with a valid color assignment that exactly reproduces the recorded matrix. It is guaranteed that Nikola’s record is correct so that at least one solution exists.

More formally, let the tree have N nodes and let c(i) denote the color of node i. For every 1 ≤ i, j ≤ N the given matrix value M[i][j] satisfies $$ M[i][j] = \Big|\{ c(x) : x \text{ lies on the unique path from } i \text{ to } j \}\Big|. $$ Find a tree (i.e. its set of N−1 edges) and a color assignment (with colors in {1,2,…,N}) such that the above equation holds for all pairs.

inputFormat

The input begins with an integer N (1 ≤ N ≤ N_max), representing the number of nodes in the tree. Following this are N lines, each containing N space‐separated integers. The j^th integer in the i^th line is M[i][j], the number of distinct colors on the unique simple path from node i to node j.

Note that for every 1 ≤ i ≤ N, M[i][i] = 1 and for any two nodes i and j, if M[i][j] = 1 then they must have the same color.

outputFormat

Output a tree and a valid color assignment that reproduces the matrix. The output should be formatted as follows:

1. Print an integer N – the number of nodes.
2. Then print N−1 lines, each containing two space‐separated integers u and v (1 ≤ u, v ≤ N) representing an edge of the tree.
3. Finally, print a line containing N space‐separated integers. The i^th integer denotes the color assigned to node i (an integer between 1 and N).

The constructed tree and color assignment must be such that for every pair of nodes i and j, the number of distinct colors on the unique path from i to j is exactly M[i][j].

sample

1
1

1
1