비결정적 유한 오토마타

비결정적 유한 오토마타(NFA)는 $G = (V, E_0, E_1, v_0, F)$로 정의한다. 여기서 $(V, E_0)$와 $(V, E_1)$는 두 개의 방향 그래프이고, $v_0 \in V$는 초기 정점, $F \subseteq V$는 수락 정점들의 집합이다.

NFA $G$가 01 문자열 $s = s_1 s_2 \ldots s_n$을 인식한다는 것은, $u_0 = v_0$이고 모든 $i = 1, 2, \ldots, n$에 대해 간선 $\langle u_{i-1}, u_i \rangle$이 $E_{s_i}$에 속하며 $u_n \in F$인 정점 수열 $u_0, u_1, \ldots, u_n$이 존재한다는 뜻이다.

$L = L(G)$는 길이가 $L$인 문자열 중 $G$가 인식하지 못하는 것이 존재하는 가장 작은 음이 아닌 정수로 정의한다. 그런 $L$이 없으면 $L(G) = -1$로 한다.

정수 $n$이 주어진다. $|V| = n$이고 $L(G)$가 충분히 큰 NFA $G = (V, E_0, E_1, v_0, F)$를 구성하라. $n$과 $L(G)$의 정확한 제약은 힌트에 있다.

첫 줄에 정수 $n$이 주어진다.

$V$의 정점은 $0, 1, \ldots, n-1$의 정수로 번호를 매긴다. 먼저 $E_0$를 출력한다. 첫 줄에는 간선 수 $e = |E_0|$ ($0 \le e \le 1000$)를 쓴다. 이어서 $e$개의 줄에 각각 정수 $x_i$와 $y_i$ ($0 \le x_i, y_i < n$)를 써서 간선 $\langle x_i, y_i \rangle \in E_0$를 나타낸다. $x_i = y_i$인 자기 루프도 허용된다.

다음으로 같은 형식으로 $E_1$을 출력한다.

그다음 정수 $k$를 한 줄에 쓰고, $F = \{f_1, f_2, \ldots, f_k\}$를 뜻하는 정수 $f_1, f_2, \ldots, f_k$를 한 줄에 쓴다.

초기 정점 $v_0$는 0으로 고정된다.

이 문제에는 $n = 6$과 $n = 20$인 두 개의 테스트가 있다.

$n = 6$일 때 출력한 NFA의 $L(G)$는 18보다 커야 한다. $n = 20$일 때는 400보다 커야 한다.