← 返回题目列表

Codeforces · 1494/D

D. 狗狗部队

中文机器翻译题面 查看原题

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

注意

第一个示例中可能的结构之一: