Problem: Problem

Multiple rooted trees are given as the initial state. Alice and Bob, on the other hand, play the game. The game is played alternately by two players, with Alice on the play and Bob on the play. The player whose turn has turned takes the following actions.

1. Select one root (vertex that has no parent). Let this vertex be S.
2. Select the vertices contained in the rooted tree rooted at S (S can also be selected here). Let this vertex be T.
3. Delete all vertices on the path from S to T, including S and T. It also deletes all edges where the deleted vertices are endpoints.



If all vertices have been deleted when the turn comes, that player loses.

When Alice and Bob always take the best action, determine which player will win against a given initial state.

The figure below shows an example of a player's actions.
Example of player behavior

Constraints

The input satisfies the following constraints.

* 1 ≤ N ≤ 1000
* 0 ≤ M <N
* i <pi ≤ N (1 ≤ i ≤ M)

Input

The input is given in the following format.


N M
p1
p2
::
pM


In the first line, the number of vertices N and the number of sides M in the initial state are given separated by blanks. At this time, the numbers representing each vertex are 1 to N. The next M line gives edge information. Of these, in line i, one integer pi is given. This means that there is an edge from vertex pi to vertex i. In other words, it means that the parent of vertex i is vertex pi.

Output

Print the name of the winning player (Alice or Bob) on one line.

Examples

Input

6 3
4
4
5


Output

Alice


Input

6 4
2
5
4
5


Output

Bob

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 1000;

int n, m;
vector<int> children[MAX_N];
int parent[MAX_N];

int memo[MAX_N];
pair<bool, int> memo2[MAX_N][MAX_N];
vector<int> nodes[MAX_N];

vector<int> calc(int v) {
  auto &res = nodes[v];
  if(!res.empty()) return res;

  res.emplace_back(v);
  for(const auto &c : children[v]) {
    const auto vec = calc(c);
    res.insert(res.end(), vec.begin(), vec.end());
  }
  return res;
}

int grundy(int v);
pair<bool, int> dfs(int v, int u) {
  auto &res = memo2[v][u];
  if(res.second != -1) return res;

  bool reach = false;
  int value = 0;
  if(v == u) {
    reach = true;
    for(const auto &c : children[v]) {
      value ^= grundy(c);
    }
  }
  else {
    vector<pair<bool, int>> buf;
    buf.reserve(children[v].size());
    for(const auto &c : children[v]) {
      buf.emplace_back(dfs(c, u));
      reach |= buf.back().first;
    }

    if(reach) {
      for(const auto &e : buf) {
	value ^= e.second;
      }
    }
    else {
      value = grundy(v);
    }
  }

  return res = make_pair(reach, value);
}

int grundy(int v) {
  int &res = memo[v];
  if(res != -1) return res;

  set<int> S;
  for(const auto &u : nodes[v]) {
    S.insert(dfs(v, u).second);
  }

  res = 0;
  while(S.count(res)) ++res;
  return res;
}

int main() {
  cin.tie(NULL);
  ios::sync_with_stdio(false);

  cin >> n >> m;

  memset(parent, -1, sizeof(parent));

  for(int i = 0; i < m; ++i) {
    int p;
    cin >> p;
    --p;

    parent[i] = p;
    children[p].emplace_back(i);
  }

  memset(memo, -1, sizeof(memo));
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < n; ++j) {
      memo2[i][j] = make_pair(false, -1);
    }
  }

  int x = 0;
  for(int v = 0; v < n; ++v) {
    if(parent[v] == -1) {
      calc(v);
      x ^= grundy(v);
    }
  }

  cout << (x != 0 ? "Alice" : "Bob") << endl;

  return 0;
}