시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB27101066.667%

문제

제이와 케이는 다리 건너기 게임을 하려고 한다. 다리 건너기 게임은 시작점에 놓여 있는 말을 도착점으로 옮기는 게임으로, N개의 섬과 몇 개의 일방통행 다리로 이루어져 있다. 섬에는 1부터 N까지의 번호가 붙어있다. 제이부터 시작하여 차례가 번갈아 가면서 진행되는데, 자신의 차례가 되면 아무것도 안 하고 건너뛰거나, 자신이 설치한 일방통행 다리를 따라 말을 옮길 수 있다. 자신의 턴에 말을 도착점인 N번 섬으로 이동시키는 사람이 게임의 승자이다.

둘은 같은 게임판으로 너무 많은 게임을 해서 직접 게임판을 제작하기로 하였다. 제이는 자신만이 이용할 수 있는 J개의 일방통행 다리를 설치했고, 케이 또한 자신만이 이용할 수 있는 K개의 일방통행 다리를 설치했다.

제이와 케이는 자신의 승리를 목표로, 그럴 수 없다면 적어도 상대의 승리를 막는 것을 목표로 플레이하고, 매번 최선의 선택을 한다. 게임이 영원히 끝나지 않아 아무도 승리하지 않을 수도 있음에 유의하라.

둘은 자신들이 만든 게임판에 애정이 생겼고, 그래서 열심히 분석을 하기로 하였다. 제이와 케이는 도착점을 제외한 N-1개의 섬이 출발점이 되었을 때의 결과를 각각 구해보려고 한다. 하지만, 너무나도 많은 분석량에 둘은 지쳐버렸다. 제이와 케이를 위해서 N-1가지의 상황에 대한 결과를 구해주자.

입력

입력의 첫 줄에 섬의 개수 N, 각각 설치한 다리 개수 J와 K가 주어진다.

그 다음 J개의 줄에는 각각 제이가 설치한 다리를 나타내는 두 정수 x, y가 주어진다. 이는 x번 섬에서 y번 섬으로 가는 다리를 나타낸다.

그 다음 K개의 줄에는 각각 케이가 설치한 다리를 나타내는 두 정수 x, y가 같은 방식으로 주어진다.

출력

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

제한

  • 2 ≤ N ≤ 100,000
  • 0 ≤ J, K ≤ 100,000
  • 1 ≤ x, y ≤ N이고, xy는 서로 다르다.

예제 입력 1

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

예제 출력 1

JJDJ

예제 입력 2

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

예제 출력 2

DDJJKK

출처

Contest > Semi-Game Cup > Semi-Game Cup 2 G번