UOJ Logo Universal Online Judge

UOJ

#460. 新年的拯救计划

附件下载 统计

DoubleDog现在锁定了 n 只SingleDog,决心去拯救它们。

为了能够快速到达这n只SingleDog的处所,DoubleDog们希望跳蚤国帮助修建一些道路,把n只SingleDog的处所联通。一条道路可以直接连接任意两只SingleDog的处所,所以只需要n1条道路就可以让它们联通。

但是糟糕的天气可能会破坏一些道路。为了能够使得DoubleDog的计划尽可能地成功,跳蚤国王决定同时修建m个方案。每个方案都包含n1条道路,任意一个方案都可以连通n只SingleDog的处所。

由于技术上的限制,跳蚤们给出了一个限制:这m个方案中任意两个方案不能存在两条相同的道路。

现在跳蚤国王想知道:最多能够选择多少个方案呢?

跳蚤国王把这个问题交给了你,请你求出这个最大的m,并告诉跳蚤国王这m个方案。

输入格式

一行一个正整数 n 表示SingleDog的数量,标号从1开始。

输出格式

输出的第一行是一个正整数 m ,表示最多能选出多少个方案。

接下来 m 行,每行 2(n1) 个数,其中第 2i1 和第 2i 个数表示该方案的一条道路。

你需要保证,这m行中任意一行的 (n1)条道路可以连通这n只SingleDog的处所,并且这m(n1)条道路互不相同。(道路(u,v)和道路(v,u)被视为相同的道路)

如果本题有多组解,输出任意一组均可。

样例一

input

3

output

1
1 2 3 2

样例二

input

4

output

2
1 2 2 3 3 4
1 3 1 4 2 4

限制与约定

本题采用捆绑测试,对于每个子任务,只有通过其中全部数据才可以获得分数。

对于 100% 的数据,3n2000

子任务编号n约定分值
1617
210010
32000n是素数44
4200029

时间限制1s

空间限制512MB

下载

样例数据下载