Graph Color Flipping Game

Alice and Bob are playing a game on a directed graph with n nodes. Each node has an initial color: black or white. The players take turns (Alice goes first) and on each turn a player selects a node u. Then, the colors of all nodes that are reachable from u (including u itself) are flipped (black becomes white and white becomes black). A move that causes all nodes to become white results in an immediate win for the player who performed that move.

Two players play optimally. Their objective is: if they can force a win they do so; otherwise, they try to avoid letting the other win. Given the initial configuration of node colors and the directed graph, determine the final outcome: whether Alice wins, Bob wins, or no one can force a win (draw).

Reachability definition:

We say that a node u can reach node v if and only if there exists a sequence of nodes \( (a_1, a_2, \dots, a_k) \) with \( k \ge 1 \) such that \( a_1 = u \), \( a_k = v \), and for every \( i \in [1, k-1] \), there is a directed edge from \( a_i \) to \( a_{i+1} \).

inputFormat

The first line contains two integers n and m (number of nodes and number of directed edges).

The second line contains a string of length n consisting only of characters 'B' and 'W'. The i-th character denotes the initial color of node i ('B' for black and 'W' for white).

The next m lines each contain two integers u and v indicating a directed edge from node u to node v. Nodes are numbered from 1 to n.

outputFormat

Output a single line: if Alice can force a win then output Alice, if Bob can force a win then output Bob, otherwise output Draw.

sample

3 3
BWB
1 2
2 3
3 1

Draw