| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 105 | 28 | 8 | 10.811% |
제이와 케이는 다리 건너기 게임이 질렸기 때문에 신작인 재생하는 다리 건너기 게임을 하려고 한다. 재생하는 다리 건너기 게임은 시작점에 놓여있는 말을 옮기는 게임으로, 게임판은 $N$개의 섬과 $M$개의 다리로 이루어져 있다. 다리는 두 섬을 양쪽 방향으로 이으며, 임의의 섬에서 다리를 따라 이동해 모든 다른 섬에 도달할 수 있다.
제이부터 시작하여 차례를 번갈아 가지며 진행되는데, 자신의 차례가 되면 다리를 따라 말을 한 칸 이동시켜야 한다. 이때, 사용한 다리는 즉시 무너져 3턴 뒤까지 사용할 수 없게 된다. 3턴이 지나고 난 후에는 다리가 재생되어 다시 사용할 수 있게 된다. 즉, 자신의 턴에 사용된 다리는 상대의 턴, 자신의 턴, 상대의 턴이 끝난 뒤 돌아오는 자신의 턴부터 다시 사용할 수 있다.
더 이상 말을 이동시킬 수 없는 사람이 게임에서 패배하게 된다. 각 $N$개의 섬이 시작점이 되었을 때의 게임의 결과를 구해보자.
첫 번째 줄에 섬의 개수 $N$, 다리의 개수 $M$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $M$개의 줄에 걸쳐 다리에 대한 정보가 주어진다. $i$번째 줄에는 $i$번 다리가 연결하는 양 끝점 $u_i,v_i$가 공백으로 구분되어 주어진다.
$N$개의 문자를 한 줄에 공백 구분 없이 출력한다. $i$번째 문자는 $i$번째 섬이 출발점일 때의 결과로, 제이가 이길 수 있다면 J, 케이가 이길 수 있다면 K, 아무도 이길 수 없으면 D이다.
5 5 1 2 2 3 3 4 4 1 3 5
JKJKK
6 7 1 3 1 4 1 5 2 3 2 4 3 4 5 6
DDDDJD