시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB0000.000%

문제

A nondeterministic finite automaton (NFA) is defined as $G = (V, E_0, E_1, v_0, F)$, where $(V, E_0)$ and $(V, E_1)$ form two directed graphs, $v_0 \in V$ is the initial vertex, and $F \subseteq V$ is the set of accepting vertices.

We say that NFA $G$ recognizes a $01$-string $s = s_1 s_2 \ldots s_n$ if and only if there exists a sequence of vertices $u_0, u_1 \ldots u_n$ such that $u_0 = v_0$, the edges $\langle u_{i - 1}, u_{i} \rangle \in E_{s_i}$ for all $i = 1, 2, \ldots, n$, and $u_n \in F$.

Define $L = L(G)$ as the minimal non-negative integer such that there exists a string $s$ of length $L$ which $G$ can not recognize. If no such $L$ exists for $G$, we define $L(G) = -1$.

You are given $n$, and you need to construct an NFA $G = (V, E_0, E_1, v_0, F)$ such that $|V| = n$ and $L(G)$ is large enough. The exact constraints on $n$ and $L(G)$ are at the bottom.

입력

The first line of input contains an integer $n$.

출력

Output the NFA $G$ you found.

Suppose the vertices in $V$ are labeled by integers $0, 1, \ldots, n - 1$.

Firstly, output $E_0$ in the following format: The first line contains an integer $e = |E_0|$ ($0 \le e \le 1000$). Then $e$ lines follow. The $i$-th of them contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i < n$), indicating that there is an edge $\langle x_i, y_i \rangle \in E_0$. Note that $x_i = y_i$ is allowed.

Secondly, print $E_1$ in the same format as $E_0$.

Next, print a line with the integer $k$.

After that, print a line containing $k$ integers $f_1, f_2, \ldots, f_k$, indicating that $F = \{f_1, f_2, \ldots, f_k\}$.

The initial vertex $v_0$ is assumed to be $0$.

예제

Below is an example that does not appear in the tests. Here, $L(G) = 4$, because $G$ cannot recognize the string "1010".

예제 입력 1

3

예제 출력 1

2
0 0
2 2
4
0 1
1 0
0 2
2 1
3
0 1 2

힌트

This problem has two tests: $n = 6$ and $n = 20$.

When $n = 6$, your output's $L(G)$ should be strictly greater than $18$.

When $n = 20$, your output's $L(G)$ should be strictly greater than $400$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.