Dogeforces 公司拥有 $$$k$$$ 员工。每个员工,除较低级别的员工外,至少有 $$$2$$$ 下属。下级员工没有下属。除公司负责人外,每位员工只有一名直接主管。公司负责人是全体员工的直接或间接监督者。众所周知,在Dogeforces中,每个主管的薪水都严格高于所有下属。
公司的完整结构是秘密的,但你知道下层员工的数量,并且对于每对下层员工,他们共同主管的工资是已知的(如果有几个这样的主管,那么工资最低的主管)。你必须恢复公司的结构。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500$$$) — 下级员工的数量。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le 5000$$$) — 带有数字的员工的普通主管的工资$$$i$$$ 和$$$j$$$。保证 $$$a_{i,j} = a_{j,i}$$$。请注意,$$$a_{i,i}$$$ 等于第 $$$i$$$ 个员工的工资。
输出
在第一行中,打印一个整数 $$$k$$$ — 公司的员工人数。
在第二行中,打印 $$$k$$$ 整数 $$$c_1, c_2, \dots, c_k$$$,其中 $$$c_i$$$ 是编号为 $$$i$$$ 的员工的工资。
在第三行中,打印一个整数 $$$r$$$ — 公司负责人的员工编号。
在下面的 $$$k-1$$$ 行中,打印两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le k$$$) — 员工及其直接主管的编号。
请注意,较低级别的员工的编号为 $$$1$$$ 到 $$$n$$$,而对于其余员工,您必须分配从 $$$n+1$$$ 到 $$$k$$$ 的编号。如果有多个正确的公司结构,您可以打印其中任何一个。
示例
输入 #1
3 2 5 7 5 1 7 7 7 4
输出 #1
5 2 1 4 7 5 4 1 5 2 5 5 4 3 4
注意
第一个示例中可能的结构之一: