路径长度各异的图

题目描述

给定整数 $L$。请构造一个满足以下条件的有向图。构造出的图可以包含重边。可以证明,满足条件的图一定存在。

• 顶点数 $N$ 不超过 $20$,所有顶点都标有 $1$ 以上 $N$ 以下且互不相同的编号

• 边数 $M$ 不超过 $60$,所有边都标有 $0$ 以上 $10^6$ 以下的整数长度

• 所有边都从编号较小的顶点指向编号较大的顶点。也就是说,$1,2,...,N$ 是按适当的拓扑序排列该图顶点编号所得出的序列

• 从顶点 $1$ 到顶点 $N$ 的不同的路径恰好有 $L$ 条,这些路径的长度是 $0$ 到 $L-1$ 之间的互不相同的整数

其中,路径的长度指该路径上所有边的长度之和。另外,两条路径不同指它们各自路径上的边的集合不同。

输入格式

输入按以下格式从标准输入给出。

$L$

输出格式

第一行输出所构造图的顶点数 $N$ 和边数 $M$。接下来的 $M$ 行中,第 $i$ 行输出 $3$ 个整数 $u_i,v_i,w_i$,分别表示第 $i$ 条边的起点、第 $i$ 条边的终点、第 $i$ 条边的长度。如果存在多个解,输出任意一个即可。

样例

4

8 10
1 2 0
2 3 0
3 4 0
1 5 0
2 6 0
3 7 0
4 8 0
5 6 1
6 7 1
7 8 1

在输出示例的图中,从顶点 $1$ 到 $N=8$ 共有 $4$ 条路径:

• 路径 $1$ → $2$ → $3$ → $4$ → $8$,长度为 $0$

• 路径 $1$ → $2$ → $3$ → $7$ → $8$,长度为 $1$

• 路径 $1$ → $2$ → $6$ → $7$ → $8$,长度为 $2$

• 路径 $1$ → $5$ → $6$ → $7$ → $8$,长度为 $3$

除此之外,还有其他会被判定为正确的输出。

5

5 7
1 2 0
2 3 1
3 4 0
4 5 0
2 4 0
1 3 3
3 5 1

数据范围

• $2 \leq L \leq 10^6$

• $L$ 是整数

提示

答案不唯一,输出任意合法解即可。