Question

Alice and Bob are playing a game on a directed graph with N vertices and M edges. Both Alice and Bob have a token which they place on some vertex (the tokens are not placed on the same vertex). In each turn a player will move their token to an adjacent vertex, the token can be moved if there is a directed edge from current vertex to the new vertex and the new vertex is not occupied by the other token. Alice always wants to move her token to a different position and Bob wants to stop her from doing that.

You need to find whether Bob can stop Alice from moving her token if Alice decides the initial position of both token and Bob moves first. If Bob can stop Alice from moving her token, you need to find the maximum number of moves Alice makes before the game ends.

Note:

The game continues even if bob is unable to move his token.

The players can not skip their turn and stay at the same position i.e if there exists some valid way to move to a new vertex, the token must be moved.

There are no self loops and cycles of length 2.

 

Constraints

2≤N≤105

1≤M≤105

 

Input format

The first line contains a single integer T (1≤T≤10), the number of testcases.

The first line of each testcase contains two integers N and M, denoting the number of vertices in the graph and the number of edges respectively.

Each of the following M lines contains two integers ui vi , denoting a edge from ui to vi.

 

Output format

For each testcase:

If Bob can stop Alice from moving her token print "Bob" without quotes and in the next line print the maximum number of moves Alice can make before the game ends else if Alice can make infinitely many moves print "Alice" without quotes.

Sample Input
1

4 4

1 2

2 3

3 1

1 4

Sample Output
Alice

 ​

Answer 1

Answer:

Alice and Bob are playing a game on a directed graph with N vertices and M edges. Both Alice and Bob have a token which they place on some vertex (the tokens are not placed on the same vertex). In each turn a player will move their token to an adjacent vertex, the token can be moved if there is a directed edge from current vertex to the new vertex and the new vertex is not occupied by the other token. Alice always wants to move her token to a different position and Bob wants to stop her from doing that.

You need to find whether Bob can stop Alice from moving her token if Alice decides the initial position of both token and Bob moves first. If Bob can stop Alice from moving her token, you need to find the maximum number of moves Alice makes before the game ends.

Note:

The game continues even if bob is unable to move his token.

The players can not skip their turn and stay at the same position i.e if there exists some valid way to move to a new vertex, the token must be moved.

There are no self loops and cycles of length 2.

 

Constraints

2≤N≤105

1≤M≤105

 

Input format

The first line contains a single integer T (1≤T≤10), the number of testcases.

The first line of each testcase contains two integers N and M, denoting the number of vertices in the graph and the number of edges respectively.

Each of the following M lines contains two integers ui vi , denoting a edge from ui to vi.

 

Output format

For each testcase:

If Bob can stop Alice from moving her token print "Bob" without quotes and in the next line print the maximum number of moves Alice can make before the game ends else if Alice can make infinitely many moves print "Alice" without quotes.

Sample Input

1

4 4

1 2

2 3

3 1

1 4

Sample Output

Alice

​

Explanation: