{"problem":{"name":"『MdOI R5』Triangulation","description":{"content":"有一个正 $n$ 边形，顶点按顺时针方向从 $1$ 到 $n$ 依次标号。给定这个多边形的 $n-3$ 条**互不相同**的对角线，满足它们**互相之间只可能在顶点处相交**。这样我们得到了一张 $n$ 个点，$2n-3$ 条边的无向图。 凸多边形的对角线指的是连接两个**不相同**且**不在多边形上相邻**的顶点的一条线段。 实际上，这个无向图可以是任意一个凸 $n$ 边形的三角剖分图。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8921"},"statements":[{"statement_type":"Markdown","content":"有一个正 $n$ 边形，顶点按顺时针方向从 $1$ 到 $n$ 依次标号。给定这个多边形的 $n-3$ 条**互不相同**的对角线，满足它们**互相之间只可能在顶点处相交**。这样我们得到了一张 $n$ 个点，$2n-3$ 条边的无向图。\n\n凸多边形的对角线指的是连接两个**不相同**且**不在多边形上相邻**的顶点的一条线段。\n\n实际上，这个无向图可以是任意一个凸 $n$ 边形的三角剖分图。\n\n你需要构造这个无向图的一棵生成树，使得每个点的度数都是**奇数**，或报告无解。\n\n## Input\n\n第一行，一个整数，表示 $n$。\n\n接下来 $n-3$ 行，每行两个整数 $u,v$ 表示一条给定的对角线 $(u,v)$。\n\n## Output\n\n如果无解，那么输出一行一个整数 $-1$。\n\n如果有解，那么输出 $n-1$ 行，每行两个数 $u,v$ 表示你所构造的答案中的一条边 $(u,v)$。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$3\\le n\\le 3\\times 10^5$。\n\n$\\operatorname{Subtask} 1(9\\%)$：$n\\le 10$。\n\n$\\operatorname{Subtask} 2(1\\%)$：$n$ 为奇数。\n\n$\\operatorname{Subtask} 3(10\\%)$：$u=1$。\n\n$\\operatorname{Subtask} 4(30\\%)$：$n\\le 100$。\n\n$\\operatorname{Subtask} 5(30\\%)$：$n\\le 5\\times 10^3$。\n\n$\\operatorname{Subtask} 6(20\\%)$：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8921","tags":["洛谷原创","Special Judge","O2优化","洛谷月赛"],"sample_group":[["5\n1 3\n1 4","-1"],["8\n6 8\n5 8\n2 4\n2 5\n1 5","3 2\n2 4\n7 8\n6 8\n2 1\n1 5\n8 1"]],"created_at":"2026-03-03 11:09:25"}}