CF1494D Dogeforces

Dogeforces 公司有 $k$ 名员工。除了基层员工外，每位员工至少有 $2$ 名下属。基层员工没有下属。除了公司负责人外，每位员工都有且仅有一位直属上司。公司负责人是所有员工的直接或间接上司。已知在 Dogeforces 公司中，每位上司的工资都严格高于其所有下属的工资。 公司的完整结构是保密的，但你知道基层员工的数量，并且对于每一对基层员工，已知他们的共同上司的工资（如果有多个这样的上司，则取工资最小的那位）。你需要还原公司的结构。

第一行包含一个整数 $n$（$2 \le n \le 500$），表示基层员工的数量。 接下来有 $n$ 行，每行包含 $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$），表示编号为 $v$ 的员工的直属上司编号。 注意：基层员工的编号为 $1$ 到 $n$，其余员工的编号为 $n+1$ 到 $k$。如果有多种正确的公司结构，你可以输出其中任意一种。

第一个样例的一种可能结构如下： 由 ChatGPT 4.1 翻译