L. Tree Game
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play a game on an undirected tree. The players start at two different nodes of the tree. The players take turns and Alice plays first. At their turn, the player must move to an empty adjacent node and can optionally decide to destroy the node they just left.

Destroyed nodes can no longer be used by the players. Note also that the tree can become a forest when nodes are destroyed.

If the two players end up in two different connected components, the game immediately ends and the player that is in the biggest component wins (if the two components are of the same size, this is considered a draw). If a player cannot move, he or she loses. Assuming both players play optimally, given the tree and the starting nodes of each player, who will win?

Input

The first three lines contain the following integers:

  • $$$N$$$ ($$$4 \leq N \leq 10^6$$$) , the number of tree nodes, numbered from 1 to N.
  • A ($$$1 \leq A \leq N$$$), Alice's start node.
  • B ($$$1 \leq B \leq N$$$ and $$$B \neq A$$$), Bob's start node.
The next $$$N - 1$$$ lines contain the edges of the tree. Each edge is represented by the two nodes it connects.
Output

A single line with either:

  • ALICE WINS
  • BOB WINS
  • DRAW
Examples
Input
4
1
4
1 2
2 3
3 4
Output
BOB WINS
Input
6
1
6
1 4
2 4
2 3
4 5
5 6
Output
DRAW
Note

Explanation of sample 1. After Alice's first move, she will be at node 2. Then Bob moves to node 3. Then Alice can only move to node 1 (unless she already destroyed it in which case she loses), and can either leave node 2 intact (in which case, Bob moves to 2 and wins by blocking Alice), or destroy node 2 (in which case, Alices ends up in the connected component {1} which is smaller than Bob's connected component {3, 4}, so she loses).

Explanation of sample 2. Alice moves from 1 to 4, then Bob moves from 6 to 5, then Alice move from 4 to 2 and destroys node 4. This disconnects the two players that are both in a connected component of size 2.