圣城鼠(mouse)
题目描述
黎瑟大一的课程里在学圣城鼠。
给定 k,构造一个 n 个节点的完全图中的 k 棵生成树 T1,…,Tk,满足任意 i=j:
- 两棵树没有公共边,即 E(Ti)∩E(Tj)=∅。
- 对任意不同节点 u,v,两棵树中从 u 到 v 的路径没有公共内部节点,即
$$\operatorname{path}_{T_i}(u,v)\cap\operatorname{path}_{T_j}(u,v)=\{u,v\}。$$
其中 pathT(u,v) 是树 T 上从 u 到 v 的路径经过的节点集合。你可以自行选择 n,要求 2≤n≤5k。
输入格式
输入一行一个正整数 k。
输出格式
第一行输出 n。节点编号为 1,…,n。
接下来输出 (n−1)k 行,每 n−1 行描述一棵生成树,每行两个整数 x,y,表示一条无向边。
整个输出不能有重复的边。可以输出任意一组合法答案,数据保证有解。
数据范围
1≤k≤100。