27502번 - 가난한 고흐와 붓 인터랙티브

책상 위에 $N$개의 숫자 카드가 놓여 있다. 카드에는 각각 $1$부터 $N$까지 서로 다른 양의 정수가 적혀 있다. 책상 밑에는 $N$개의 빈 상자가 놓여 있다. 상자에도 각각 $1$부터 $N$까지 서로 다른 양의 정수가 적혀 있다. 고흐와 당신은 번갈아 가며 책상 위에 놓인 원하는 숫자 카드 하나를 집어서 원하는 빈 상자에 넣는 행위를 책상 위에서 카드가 사라질 때까지 반복한다. 이때 카드를 넣을 상자는 반드시 비어있어야 한다.

$N$개의 숫자 카드를 상자에 모두 넣고 나면, 칠판에 간선은 없고 정점만 $N$개 있는 그래프에 간선을 그릴 것이다. $N$개의 상자 각각에 대해 $i$번 상자에 들어있는 카드를 $A_i$라고 하면 $i$번 정점과 $A_i$번 정점을 양방향 간선으로 연결한다. 이 과정에서 어떤 정점에서 자기 자신으로 바로 연결된 간선이 생길 수도 있고, 두 정점 사이의 간선이 여러 개 생길 수도 있다.

$N$개의 간선이 그려지면 고흐는 다음의 행동을 원하는 만큼 반복해 모든 간선을 색칠해야 한다.

1. 새로운 붓을 꺼낸다.
2. 원하는 정점에서 시작해 색칠되지 않은 간선을 칠한다.

정점 $x$와 정점 $y$를 연결하는 간선이 있을 때 $x$에서 $y$로 붓을 이동시키거나, $y$에서 $x$로 붓을 이동시키면 간선을 색칠할 수 있다. 고흐는 하나의 붓으로 여러 개의 이어진 간선들을 색칠할 수 있다. 예를 들어 $x$에서 $y$로 붓을 이동시키고, $y$에서 $z$로 붓을 이동시키면 같은 붓으로 간선을 $2$개 색칠하고 붓은 $z$에 위치하게 된다. 그러나 이미 색칠한 간선을 다시 칠할 수는 없다. 그러므로 $x$에서 $y$로 붓을 이동시키고, 같은 간선을 통해 다시 $x$로 붓을 이동시킬 수는 없다.

고흐는 최소한의 붓을 사용해 모든 간선을 색칠하려고 한다. 반면 당신은 고흐가 최대한 많은 붓을 사용하도록 상자에 카드를 넣을 것이다. 고흐는 최선을 다해 붓의 개수를 줄이려고 노력한다.

카드의 개수 $N$이 주어진다. ($N$은 짝수, $2 \leq$ $N$ $\leq 2\,000$)

이어 $t$가 주어진다. $t$가 $0$이면 고흐가 먼저 카드를 상자에 넣는다. $t$가 $1$이면 당신이 먼저 카드를 상자에 넣는다.

표준 출력 스트림(stdout)으로 서로 최선을 다했을 때 고흐가 사용하는 붓의 개수 $k$를 다음과 같이 출력한다. 출력한 후에는 반드시 개행 문자를 출력하고 표준 출력 버퍼를 flush해야 한다.

• ! $k$ : 고흐가 사용하는 붓의 개수

이어서 $t$가 $0$이면 고흐부터, $t$가 $1$이면 당신부터 카드를 상자에 넣는다.

고흐 차례에는 표준 입력 스트림(stdin)을 통해 숫자 $2$개를 입력 받아야 한다.

• $a$ $b$ : 고흐가 $a$번 카드를 $b$번 상자에 넣는다.

당신 차례에는 표준 출력 스트림(stdout)으로 숫자 $2$개를 출력해야 한다. 두 숫자를 출력한 후에는 반드시 개행 문자를 출력하고 표준 출력 버퍼를 flush해야 한다.

• $a$ $b$ : 당신이 $a$번 카드를 $b$번 상자에 넣는다.

당신이 잘못된 $k$를 출력했거나, 불가능한 행위를 한 경우(예: 없는 카드를 상자에 넣는 행위, 비어있지 않은 상자에 카드를 넣는 행위) 프로그램은 즉시 종료되고, 오답 판정을 받는다.

언어별로 표준 출력 버퍼를 flush하는 방법은 출력 명령문 바로 아래 줄에 다음과 같은 문장을 추가하면 된다.

• C: fflush(stdout);
• C++: std::cout << std::flush;
• Java: System.out.flush();
• Python: sys.stdout.flush()