시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB10528810.811%

문제

제이와 케이는 다리 건너기 게임이 질렸기 때문에 신작인 재생하는 다리 건너기 게임을 하려고 한다. 재생하는 다리 건너기 게임은 시작점에 놓여있는 말을 옮기는 게임으로, 게임판은 $N$개의 섬과 $M$개의 다리로 이루어져 있다. 다리는 두 섬을 양쪽 방향으로 이으며, 임의의 섬에서 다리를 따라 이동해 모든 다른 섬에 도달할 수 있다.

제이부터 시작하여 차례를 번갈아 가지며 진행되는데, 자신의 차례가 되면 다리를 따라 말을 한 칸 이동시켜야 한다. 이때, 사용한 다리는 즉시 무너져 3턴 뒤까지 사용할 수 없게 된다. 3턴이 지나고 난 후에는 다리가 재생되어 다시 사용할 수 있게 된다. 즉, 자신의 턴에 사용된 다리는 상대의 턴, 자신의 턴, 상대의 턴이 끝난 뒤 돌아오는 자신의 턴부터 다시 사용할 수 있다.

더 이상 말을 이동시킬 수 없는 사람이 게임에서 패배하게 된다. 각 $N$개의 섬이 시작점이 되었을 때의 게임의 결과를 구해보자.

입력

첫 번째 줄에 섬의 개수 $N$, 다리의 개수 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$개의 줄에 걸쳐 다리에 대한 정보가 주어진다. $i$번째 줄에는 $i$번 다리가 연결하는 양 끝점 $u_i,v_i$가 공백으로 구분되어 주어진다.

출력

$N$개의 문자를 한 줄에 공백 구분 없이 출력한다. $i$번째 문자는 $i$번째 섬이 출발점일 때의 결과로, 제이가 이길 수 있다면 J, 케이가 이길 수 있다면 K, 아무도 이길 수 없으면 D이다.

제한

  • $1\le N\le 5\, 000$
  • $N-1\le M\le 5\, 000$
  • 각 $1\le i\le N$에 대하여, $1\le u_i,v_i\le N$이고 $u_i\neq v_i$
  • 두 섬 쌍을 잇는 다리는 최대 하나만 주어진다.
  • 임의의 섬에서 다리를 따라 이동해 모든 다른 섬에 도달할 수 있다.

예제 입력 1

5 5
1 2
2 3
3 4
4 1
3 5

예제 출력 1

JKJKK

예제 입력 2

6 7
1 3
1 4
1 5
2 3
2 4
3 4
5 6

예제 출력 2

DDDDJD

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final H번