#P6933. 林海的密码
林海的密码
题目描述
土地精灵给了小 D 一个整数 ,要求他用一个有标号有向图解开法阵。
你要构造一个图,顶点编号为 ,使得以顶点 为根的内向生成树恰有 棵。内向生成树中,每个非根顶点沿树边都能走到根。图可以包含重边和自环。平行边按不同的边计数。
设图有 条边,需要满足 和 。
输入格式
一行三个正整数 。保证存在满足限制的构造。
输出格式
第一行输出 。
随后输出 行,每行两个整数 ,表示一条从 指向 的有向边。
样例
1 114514 1919810
3 4
1 2
2 1
2 3
3 2
数据范围
。下表为原赛各子任务的限制,原赛须通过同一子任务的全部测试点才能获得该子任务的分数。
| 子任务 | 原赛分值 | 对 的特殊限制 | ||
|---|---|---|---|---|
| 1 | 15 | 130 | 400 | |
| 2 | , | |||
| 3 | 30 | |||
| 4 | 20 | |||
| 5 | 80 | 220 |