题目描述

Gennady and Georgiy are playing interesting game on a directed graph. The graph has $n$ vertices and $m$ arcs, loops are allowed. Gennady and Georgiy have a token placed in one of the graph vertices. Players take turns moving the token along one of the arcs that starts in the vertex the token is currently in. When there is no such arc, then this player loses the game.

For each initial position of the token and the player who is moving first, your task is to determine what kind of result the game is going to have. Does it seem to be easy? Not so much.

On one side, Gennady is having a lot of fun playing this game, so he wants to play as long as possible. He even prefers a strategy that leads to infinite game to a strategy that makes him a winner. But if he cannot make the game infinite, then he obviously prefers winning to losing.

On the other side, Georgiy has a lot of other work, so he does not want to play the game infinitely. Georgiy wants to win the game, but if he cannot win, then he prefers losing game to making it infinite.

Both players are playing optimally. Both players know preferences of the other player.

输入格式

In the first line there are two integers -- the number of vertices $n (1 \le n \le 100 000)$ and the number of arcs $m (1 \le m \le 200 000)$ . In the next $m$ lines there are two integers a and $b$ on each line, denoting an arc from vertex a to vertex $b$ . Vertices are numbered from $1$ to $n$ . Each $(a , b)$ tuple appears at most once.

输出格式

In the first line print $n$ characters -- i-th character should denote the result of the game if Gennady starts in vertex $i$ . In the second line print $n$ characters -- i-th character should denote the result of the game if Georgiy starts in vertex $i$ . The result of the game is denoted by W if the starting player wins the game, L if the starting player loses the game, and D (draw) if the game runs infinitely.

题目大意

Gennady 和 Georgiy 在玩一个有向图上的游戏。这个图有 $n$ 个点 $m$ 条边，两人轮流操作，每次可以将棋子沿着其中一条边移动，不能移动者输。

你要对于每个点，分别求出以这个店为起点开始游戏，两人分别作为先手，最终会输，赢，还是平局（游戏无限循环）。

其中，Gennady 因为玩得很开心，所以他更期望将游戏变为平局；Georgiy 还有很多其他事，所以他更期望游戏不要平局。当然，在不平局的基础上，两人都更希望赢。

输入格式

第一行两个数 $n$，$m$ 表示有 $n$ 个点 $m$ 条边。
接下来 $m$ 行每行两个数 $a,b$ 表示一条由 $a$ 至 $b$ 的边。

输出格式

两行，第一行表示分别以每一个点为起点 Gennady 先手的胜负情况；第二行表示分别以每一个点为起点 Georgiy 先手的胜负情况。W 表示赢，L 表示输，D 表示平局。

by a___

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

WDLDWL
DWLLWL 

提示

Time limit: 2 s, Memory limit: 512 MB.