항공 노선도

앨리스는 JOI 왕국에 살고 있다. 그녀는 IOI 공화국에 사는 밥을 초대하려고 한다. 초대하기 전에 JOI 왕국의 항공 노선도를 밥에게 보내고 싶어 한다.

JOI 왕국은 $0$부터 $N-1$까지 번호가 붙은 $N$개의 섬으로 이루어진 섬나라이다. 항공 노선은 $M$개 있다. 각 $i$ ($0 \le i \le M-1$)에 대해, $(i+1)$번째 노선은 섬 $A_i$와 섬 $B_i$를 양방향으로 잇는다. 같은 두 섬을 잇는 노선은 없다.

앨리스는 JOI 왕국이 운영하는 특수 전신기로 노선도를 보내야 한다. 이 기계는 무방향 그래프를 보낼 수 있다. 다만 전송 과정에서 정점 번호와 간선 번호가 무작위로 섞인다.

정확히 말하면 정보는 다음과 같이 전송된다. 앨리스가 보내는 그래프를 $G$라 하고, $G$의 정점 수를 $V$, 간선 수를 $U$라 하자.

• 앨리스는 $V$와 $U$를 정한다. 정점에는 $0, 1, \ldots, V-1$을, 간선에는 $0, 1, \ldots, U-1$을 번호로 붙인다.
• 앨리스는 매개변수 $C_0, \ldots, C_{U-1}$과 $D_0, \ldots, D_{U-1}$을 정한다. $j$번째 간선은 정점 $C_j$와 정점 $D_j$를 잇는다.
• JOI 왕국이 정점 번호를 섞는다. $0, \ldots, V-1$의 순열 $p[0], \ldots, p[V-1]$을 만든 뒤, 모든 $j$에 대해 $C_j$를 $p[C_j]$로, $D_j$를 $p[D_j]$로 바꾼다.
• JOI 왕국이 간선 번호를 섞는다. $0, \ldots, U-1$의 순열 $q[0], \ldots, q[U-1]$을 만든 뒤, 새 $C_j$가 옛 $C_{q[j]}$, 새 $D_j$가 옛 $D_{q[j]}$가 되도록 재배열한다.
• 밥은 $V$, $U$와 최종 $C_0, \ldots, C_{U-1}$, $D_0, \ldots, D_{U-1}$ 값을 받는다.

이 기계로는 단순 그래프만 보낼 수 있다. $i \ne j$이면 $(C_i, D_i)$는 $(C_j, D_j)$와 달라야 하고, $(C_i, D_i)$는 $(D_j, C_j)$와도 달라야 한다. 모든 $i$에 대해 $C_i \ne D_i$이어야 한다.

앨리스는 정점 수가 가장 적은 그래프로 노선도를 보내려고 한다.

두 프로그램을 작성해야 한다.

• $N$, $M$, 수열 $A$, $B$가 주어지면, 첫 번째 프로그램은 앨리스가 보낼 그래프 $G$의 정보를 출력한다.
• 밥이 받은 그래프 $G$의 정보가 주어지면, 두 번째 프로그램은 JOI 왕국의 항공 노선도를 복원한다.

샘플 채점기는 표준 입력에서 다음 데이터를 읽는다.

• 첫 줄에는 공백으로 구분된 정수 $N$과 $M$이 있다. JOI 왕국에는 섬이 $N$개, 항공 노선이 $M$개 있다.
• 이어지는 $M$줄은 노선도를 나타낸다. 그중 $(i+1)$번째 줄에는 공백으로 구분된 정수 $A_i$와 $B_i$가 있다.

프로그램이 오답으로 판정되면 샘플 채점기는 Wrong Answer [1] 형식으로 오답 유형을 출력하고 종료한다.

Alice 호출과 Bob 호출이 모두 오답으로 판정되지 않으면 채점기는 Accepted.를 출력한 뒤 $V$의 값을 출력한다.

여러 유형의 오답에 해당하면 채점기는 그중 하나만 보고한다.

• $1 \le N \le 1000$.
• $0 \le M \le N(N-1)/2$.
• $0 \le A_i \le N-1$ ($0 \le i \le M-1$).
• $0 \le B_i \le N-1$ ($0 \le i \le M-1$).
• $A_i \ne B_i$ ($0 \le i \le M-1$).
• $(A_i, B_i) \ne (A_j, B_j)$이고 $(A_i, B_i) \ne (B_j, A_j)$ ($0 \le i < j \le M-1$).