『MdOI R5』Triangulation

Luogu

IDLGP8921

Time1000ms

Memory512MB

DifficultyP5

洛谷原创Special JudgeO2优化洛谷月赛

有一个正 $n$ 边形，顶点按顺时针方向从 $1$ 到 $n$ 依次标号。给定这个多边形的 $n-3$ 条**互不相同**的对角线，满足它们**互相之间只可能在顶点处相交**。这样我们得到了一张 $n$ 个点，$2n-3$ 条边的无向图。凸多边形的对角线指的是连接两个**不相同**且**不在多边形上相邻**的顶点的一条线段。实际上，这个无向图可以是任意一个凸 $n$ 边形的三角剖分图。你需要构造这个无向图的一棵生成树，使得每个点的度数都是**奇数**，或报告无解。 ## Input 第一行，一个整数，表示 $n$。接下来 $n-3$ 行，每行两个整数 $u,v$ 表示一条给定的对角线 $(u,v)$。 ## Output 如果无解，那么输出一行一个整数 $-1$。如果有解，那么输出 $n-1$ 行，每行两个数 $u,v$ 表示你所构造的答案中的一条边 $(u,v)$。 [samples] ## Note 对于 $100\%$ 的数据，$3\le n\le 3\times 10^5$。 $\operatorname{Subtask} 1(9\%)$：$n\le 10$。 $\operatorname{Subtask} 2(1\%)$：$n$ 为奇数。 $\operatorname{Subtask} 3(10\%)$：$u=1$。 $\operatorname{Subtask} 4(30\%)$：$n\le 100$。 $\operatorname{Subtask} 5(30\%)$：$n\le 5\times 10^3$。 $\operatorname{Subtask} 6(20\%)$：无特殊限制。

Samples

Input #1

5
1 3
1 4

Output #1

-1

Input #2

Output #2

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments