{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e♔♕♖♗♘♙♚♛♜♝♞♟\u003c/p\u003e\n\n\u003cp\u003eDogeforces 公司有 $$$k$$$ 名员工。除了底层员工外,每位员工至少有 $$$2$$$ 个下属。底层员工没有下属。除了公司负责人外,每位员工都有且只有一个直接主管。公司负责人是所有员工的直接或间接主管。已知在 Dogeforces 公司中,每位主管的薪水严格高于他的所有下属。\u003c/p\u003e\u003cp\u003e公司的完整结构是秘密的,但你知道底层员工的数量,以及对于每对底层员工,他们共同主管的薪水(如果有多位这样的主管,则选择薪水最低的主管)。你需要恢复公司的结构。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$n$$$ ($$$2 \\le n \\le 500$$$) — 公司底层员工的数量。\u003c/p\u003e\u003cp\u003e接下来的 $$$n$$$ 行,每行包含 $$$n$$$ 个整数 $$$a_{i,1}, a_{i,2}, \\dots, a_{i,n}$$$ ($$$1 \\le a_{i,j} \\le 5000$$$) — 控制员工编号为 $$$i$$$ 和 $$$j$$$ 的员工的共同主管的薪水。保证 $$$a_{i,j} \u003d a_{j,i}$$$。注意 $$$a_{i,i}$$$ 等于第 $$$i$$$ 位员工的薪水。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e第一行输出一个整数 $$$k$$$ — 公司员工的总数。\u003c/p\u003e\u003cp\u003e第二行输出 $$$k$$$ 个整数 $$$c_1, c_2, \\dots, c_k$$$,其中 $$$c_i$$$ 是员工编号为 $$$i$$$ 的员工的薪水。\u003c/p\u003e\u003cp\u003e第三行输出一个整数 $$$r$$$ — 公司负责人的员工编号。\u003c/p\u003e\u003cp\u003e接下来的 $$$k-1$$$ 行,每行输出两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \\le v, u \\le k$$$) — 员工的编号和他的直接主管的编号。\u003c/p\u003e\u003cp\u003e注意,底层员工的编号从 $$$1$$$ 到 $$$n$$$,对于其余员工,你需要分配从 $$$n+1$$$ 到 $$$k$$$ 的编号。如果存在多种正确的公司结构,你可以输出其中任意一种。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2 5 7\n5 1 7\n7 7 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n2 1 4 7 5 \n4\n1 5\n2 5\n5 4\n3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个示例中可能的一种结构是: \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/3eeb1b1fd47b49f2303c05fb4e31df40?v\u003d1717071282\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}