D. Skill Issue
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are preparing for a gaming tournament. The house has $$$n$$$ devices, with $$$m$$$ cables already directly connecting some pairs of them.

Alice plays on device $$$a$$$, Bob plays on device $$$b$$$, and the main router is device $$$c$$$. Every cable adds one unit of delay. To get the fastest connection, they want as few cables as possible between their device and the router.

They take turns adding one new cable between two devices. The only rule: the two devices must not already be connected by a sequence of cables — otherwise the cables would form a cycle, and a signal looping round and round would crash the network. The game ends when no more cables can be added.

Let $$$d(x, y)$$$ be the number of cables on the simple path between devices $$$x$$$ and $$$y$$$ at the end.

  • If $$$d(a, c) \lt d(b, c)$$$, Alice gets the better connection and wins.
  • If $$$d(b, c) \lt d(a, c)$$$, Bob gets the better connection and wins.
  • If $$$d(a, c) = d(b, c)$$$, it is a tie.

Alice plugs in the first cable. Both gamers play perfectly: they will always make a move to secure a win if one exists. If winning is completely impossible, they will fiercely defend to force a tie rather than lose. What is the result of the game?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$, $$$0 \le m \lt n$$$) — the number of devices and the number of existing cables, respectively.

The second line of each test case contains three distinct integers $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a, b, c \le n$$$) — the device where Alice plays, the device where Bob plays, and the device where the main router is located, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — an existing cable connecting devices $$$u$$$ and $$$v$$$. It is guaranteed that the initial network contains no cycles.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print a single line: Alice if Alice secures a faster connection, Bob if Bob does, or Tie if their connection speeds end up equal.

Example
Input
2
7 4
1 2 3
4 3
2 5
5 6
6 3
7 3
1 2 3
1 4
2 5
3 6
Output
Alice
Tie
Note

For the first sample test case, Alice adds a cable between $$$1$$$ and $$$4$$$. Bob adds a cable between $$$3$$$ and $$$7$$$. The game ends. $$$d(1, 3) = 2$$$ and $$$d(2, 3) = 3$$$. Alice wins.