#P8688. [2018山东省队集训第一轮]圣城⿏

    ID: 8778 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>图论数据结构动态规划CF1800构造数学树形DP

[2018山东省队集训第一轮]圣城⿏

圣城鼠(mouse)

题目描述

黎瑟大一的课程里在学圣城鼠。

给定 kk,构造一个 nn 个节点的完全图中的 kk 棵生成树 T1,…,TkT_1,\ldots,T_k,满足任意 i≠ji\ne j:

  1. 两棵树没有公共边,即 E(Ti)∩E(Tj)=∅E(T_i)\cap E(T_j)=\varnothing。
  2. 对任意不同节点 u,vu,v,两棵树中从 uu 到 vv 的路径没有公共内部节点,即
$$\operatorname{path}_{T_i}(u,v)\cap\operatorname{path}_{T_j}(u,v)=\{u,v\}。$$

其中 path⁡T(u,v)\operatorname{path}_T(u,v) 是树 TT 上从 uu 到 vv 的路径经过的节点集合。你可以自行选择 nn,要求 2≤n≤5k2\le n\le5k。

输入格式

输入一行一个正整数 kk。

输出格式

第一行输出 nn。节点编号为 1,…,n1,\ldots,n。

接下来输出 (n−1)k(n-1)k 行,每 n−1n-1 行描述一棵生成树,每行两个整数 x,yx,y,表示一条无向边。

整个输出不能有重复的边。可以输出任意一组合法答案,数据保证有解。

数据范围

1≤k≤1001\le k\le100。