Dogeforces

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$) — the number of lower-level employees.

This is followed by $$$n$$$ lines, where $$$i$$$-th line contains $$$n$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le 5000$$$) — salary of the common supervisor of employees with numbers $$$i$$$ and $$$j$$$. It is guaranteed that $$$a_{i,j} = a_{j,i}$$$. Note that $$$a_{i,i}$$$ is equal to the salary of the $$$i$$$-th employee.

Output:

In the first line, print a single integer $$$k$$$ — the number of employees in the company.

In the second line, print $$$k$$$ integers $$$c_1, c_2, \dots, c_k$$$, where $$$c_i$$$ is the salary of the employee with the number $$$i$$$.

In the third line, print a single integer $$$r$$$ — the number of the employee who is the head of the company.

In the following $$$k-1$$$ lines, print two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le k$$$) — the number of the employee and his direct supervisor.

Note that the lower-level employees have numbers from $$$1$$$ to $$$n$$$, and for the rest of the employees, you have to assign numbers from $$$n+1$$$ to $$$k$$$. If there are several correct company structures, you can print any of them.

Sample Input:

3
2 5 7
5 1 7
7 7 4

Sample Output:

5
2 1 4 7 5 
4
1 5
2 5
5 4
3 4

Note:

One of the possible structures in the first example: