#P6933. 林海的密码

林海的密码

题目描述

土地精灵给了小 D 一个整数 CC,要求他用一个有标号有向图解开法阵。

你要构造一个图,顶点编号为 1,2,…,n1,2,\ldots,n,使得以顶点 nn 为根的内向生成树恰有 CC 棵。内向生成树中,每个非根顶点沿树边都能走到根。图可以包含重边和自环。平行边按不同的边计数。

设图有 mm 条边,需要满足 1≤n≤limV1\le n\le\mathrm{limV} 和 0≤m≤limE0\le m\le\mathrm{limE}。

输入格式

一行三个正整数 C,limV,limEC,\mathrm{limV},\mathrm{limE}。保证存在满足限制的构造。

输出格式

第一行输出 n,mn,m。

随后输出 mm 行,每行两个整数 u,vu,v,表示一条从 vv 指向 uu 的有向边。

样例

1 114514 1919810
3 4
1 2
2 1
2 3
3 2

数据范围

1≤C≤10181\le C\le10^{18}。下表为原赛各子任务的限制,原赛须通过同一子任务的全部测试点才能获得该子任务的分数。

子任务 原赛分值 limV\mathrm{limV} limE\mathrm{limE} 对 CC 的特殊限制
1 15 130 400 C≤100C\le100
2 C=2kC=2^k,0≤k≤200\le k\le20
3 30 C≤109C\le10^9
4 20 C≤1018C\le10^{18}
5 80 220

原 PDF 题面