#P8683. [2018山东省队集训第一轮]解决npc

    ID: 8773 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>数论图论CF2200构造数学递归搜索回溯法

[2018山东省队集训第一轮]解决npc

解决 npc(npc)

题目描述

作为 OI 大师,某数字同学经常能解决一些 npc 问题,比如有向图拓扑序计数。 咕咕同学决定出道题来考一考他到底会不会有向图拓扑计数。

咕咕同学打算给某数字同学一个有向无环图,让他来数一数到底有多少种本质不同的拓扑序。

但是咕咕同学在出数据的时候,他想要控制某数字同学的输出,所以他想要生成一张有向无环图,使得它的本质不同的拓扑序恰好为xx。

因为咕咕同学的电脑实在是太小了,所以点数不能超过 5050 个,边数不能超过 100100 个。

因为咕咕同学并不会解决 npc 问题,所以xx并不会太大,不然他就不会写 spj 了。

输入格式

从标准输入读入。第一行一个正整数 x, 意义如题面所示。

输出格式

向标准输出写出。第一行一个正整数 nn 和一个非负整数 mm, 表示这张 DAG 的点数和边数。 接下来mm行,每行两个正整数x,y,x,y, 表示存在一条从xx到yy 的边。 节点编号为 0,1,…,n−10,1,\ldots,n-1。可以输出任意一组满足要求的图。

样例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

子任务

对于 2020% 的数据,x≤40x\le40。 对于 100100% 的数据,x≤32767x\le32767。