注意

此处的数据是民间数据，仅供参考。

你可以在右边一栏点击「下载」以下载民间数据。

题目描述

小可可需要你构造一个 $n$ 个点 $m$ 条边且无重边的有向无环图（节点从 $1$ 开始标号），其中点 $1$ 的入度和点 $n$ 的出度必须为 $0$。并且，对于 $0 \sim p$ 中的每一个整数 $i$，都能通过保留图中的一部分有向边使得从点 $1$ 到点 $n$ 的不同路径方案数为 $i$。请给出你构造的有向无环图以及对于每一个 $i$ 需要保留哪些边。

答案不唯一，因此你只需输出任意一种可行方案，详见输出格式。你可以自己指定 $\bm{n, m}$ 的大小，但必须保证 $\bm{n \le 24, m \le 65}$。

一条经过 $|P|$ 个点的，从点 $1$ 到点 $n$ 的路径 $P$ 可以描述为一个长度为 $|P|$ 的序列 $(P_1, P_2, \ldots, P_{|P|})$，其中 $P_1 = 1, P_{|P|} = n$，并且对于 $i = 1, 2, \ldots, |P| - 1$，图中都存在 $P_i \to P_{i + 1}$ 的有向边。

两条路径 $A, B$ 不同，当且仅当 $|A| \ne |B|$，或者存在一个 $1 \sim |A|$ 中的正整数 $i$，使得 $A_i \ne B_i$。

输入格式

输入仅有一行一个正整数 $p$。

输出格式

第一行输出两个正整数 $n, m$ 表示你构造的有向无环图的点数和边数。

接下来 $m$ 行，第 $i$ 行输出两个正整数 $u, v$ 表示图中的第 $i$ 条有向边 $u \to v$。

接下来 $p + 1$ 行，第 $i$ 行输出一个长度为 $m$ 的仅由 01 构成的字符串，表示要使得点 $1$ 到点 $n$ 的不同路径方案数为 $i - 1$ 的情况下选择保留哪些边，从左到右第 $j$ 个字符若为 $1$ 表示保留第 $j$ 条边，$0$ 表示不保留。

样例

3

5 6
1 2
2 5
1 3
3 5
1 4
4 5
000000
110000
111100
111111

样例解释

样例的 $\bm p$ 不满足数据范围，因此不会出现在测试数据中。

样例中 $p = 3$。下图是样例输出中构造出的一种可行的图。

当六条边全部不选的时候，显然点 $1$ 无法到达点 $5$，方案数为 $0$。

仅保留第 $1, 2$ 条边时，点 $1$ 到点 $5$ 仅有一条路径可选（$1 \to 2 \to 5$），方案数为 $1$。

保留第 $1, 2, 3, 4$ 条边时，点 $1$ 到点 $5$ 有两条路径可选（$1 \to 2 \to 5$ 和 $1 \to 3 \to 5$），方案数为 $2$。

所有边全部保留时，点 $1$ 到点 $5$ 有三条路径可选（$1 \to 2 \to 5$，$1 \to 3 \to 5$ 和 $1 \to 4 \to 5$），方案数为 $3$。

因此，这组构造方案是合法的。

数据范围

对于 $100\%$ 的数据，$5 \le p \le 75000$。

本题共有 $20$ 个测试点：