그래프 위의 게임

겐나디와 게오르기가 방향 그래프에서 게임을 한다. 그래프에는 정점이 $n$개, 간선이 $m$개 있고, 자기 자신으로 돌아오는 간선도 있을 수 있다. 말은 정점 하나에 놓여 있다. 두 사람은 번갈아 가며 말이 놓인 정점에서 나가는 간선 하나를 골라 그 간선을 따라 말을 옮긴다. 자기 차례에 옮길 간선이 없는 사람이 진다.

두 사람이 바라는 결과는 서로 다르다. 겐나디는 이 게임이 재미있어서 최대한 오래 하고 싶어 한다. 그래서 이기는 것보다 게임이 끝나지 않는 쪽을 더 좋아하고, 지는 것보다는 이기는 쪽을 더 좋아한다. 게오르기는 다른 할 일이 많아서 끝나지 않는 게임을 가장 싫어한다. 이기는 쪽을 가장 좋아하고, 게임이 끝나지 않을 바에는 차라리 지는 쪽을 고른다.

두 사람 모두 최선을 다해서 두고, 상대가 어떤 결과를 더 좋아하는지도 안다.

말의 시작 정점과 먼저 두는 사람이 정해졌을 때 게임이 어떻게 끝나는지 모두 구하라.

첫째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 주어진다 ($1 \le n \le 100\,000$, $1 \le m \le 200\,000$). 다음 $m$개의 줄에는 각각 두 정수 $a$와 $b$가 주어지고, 정점 $a$에서 정점 $b$로 가는 간선을 뜻한다 ($1 \le a, b \le n$). 정점 번호는 1부터 $n$까지이며, 같은 순서쌍 $(a, b)$가 두 번 이상 주어지지는 않는다.

$n$개의 문자로 이루어진 줄을 두 줄 출력한다. 첫째 줄의 $i$번째 문자는 말이 정점 $i$에 놓이고 겐나디가 먼저 둘 때의 결과이고, 둘째 줄의 $i$번째 문자는 말이 정점 $i$에 놓이고 게오르기가 먼저 둘 때의 결과이다. 먼저 두는 사람이 이기면 W, 지면 L, 게임이 끝나지 않으면 D를 쓴다.