Optimal Card Discard Strategy

Alice and Bob each have \(n\) cards numbered from \(1\) to \(n\). They play exactly \(n-1\) rounds. In each round, Alice first discards one card from Bob’s set, and then Bob discards one card from Alice’s set. At the end, each player is left with exactly one card.

There are \(m\) special relations given. Each relation is described by a triple \(x\), \(y\) and a result letter such that if Alice’s final card is \(x\) and Bob’s final card is \(y\), then the result is either a win or a loss for Alice. More formally, a relation is given as:

[ \text{if } (x,y) \text{ then Alice } \begin{cases} \text{wins} &\text{if the relation letter is } W,\ \text{loses} &\text{if the relation letter is } L. \end{cases} ]

Any final pair \((x,y)\) that is not specified by a relation results in a draw. Both players play with optimal strategies. Here optimal strategy means that if a winning strategy is available a player will choose it; otherwise, if a drawing strategy is available, the player will choose it. Under optimal play, determine whether Alice will eventually win, lose, or the game ends in a draw.

inputFormat

The first line of input contains two integers \(n\) and \(m\) (where \(1 \leq n \leq 15\) and \(0 \le m \leq n^2\)).

Then \(m\) lines follow. Each of these lines contains two integers \(x\) and \(y\) (\(1 \le x,y \le n\)) and a character which is either W or L. Here, W indicates that if Alice’s final card is \(x\) and Bob’s final card is \(y\), then Alice wins, and L indicates that Alice loses.

If a pair \((x,y)\) is not specified, the outcome is a draw.

outputFormat

Output a single line containing one of the following strings:

• Alice wins if Alice can force a win,
• Alice loses if Bob can force a loss for Alice, or
• Draw if the game will end in a draw under optimal play.

sample

2 1
1 2 W

Draw