#P8683. [2018山东省队集训第一轮]解决npc
[2018山东省队集训第一轮]解决npc
解决 npc(npc)
题目描述
作为 OI 大师,某数字同学经常能解决一些 npc 问题,比如有向图拓扑序计数。 咕咕同学决定出道题来考一考他到底会不会有向图拓扑计数。
咕咕同学打算给某数字同学一个有向无环图,让他来数一数到底有多少种本质不同的拓扑序。
但是咕咕同学在出数据的时候,他想要控制某数字同学的输出,所以他想要生成一张有向无环图,使得它的本质不同的拓扑序恰好为。
因为咕咕同学的电脑实在是太小了,所以点数不能超过 个,边数不能超过 个。
因为咕咕同学并不会解决 npc 问题,所以并不会太大,不然他就不会写 spj 了。
输入格式
从标准输入读入。第一行一个正整数 x, 意义如题面所示。
输出格式
向标准输出写出。第一行一个正整数 和一个非负整数 , 表示这张 DAG 的点数和边数。 接下来行,每行两个正整数 表示存在一条从到 的边。 节点编号为 。可以输出任意一组满足要求的图。
样例1输入
51
样例1输出
27 49
0 2
1 3
0 3
3 4
0 4
4 5
0 5
5 6
0 6
6 7
0 7
7 8
0 8
8 9
0 9
9 10
0 10
10 11
0 11
11 12
0 12
12 13
0 13
13 14
0 14
14 15
0 15
15 16
0 16
16 17
0 17
17 18
0 18
18 19
0 19
19 20
0 20
20 21
0 21
21 22
0 22
22 23
0 23
23 24
0 24
24 25
0 25
25 26
0 26
子任务
对于 % 的数据,。 对于 % 的数据,。