#include <bits/stdc++.h>
using namespace std;
class range {
 private:
  struct Iter {
    int v;
    int operator*() { return v; }
    bool operator!=(Iter& itr) { return v < itr.v; }
    void operator++() { ++v; }
  };
  Iter i, n;

 public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iter& begin() { return i; }
  Iter& end() { return n; }
};
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  return is >> p.first >> p.second;
}
template <typename T1>
istream& operator>>(istream& is, tuple<T1>& t) {
  return is >> get<0>(t);
}
template <typename T1, typename T2>
istream& operator>>(istream& is, tuple<T1, T2>& t) {
  return is >> get<0>(t) >> get<1>(t);
}
template <typename T1, typename T2, typename T3>
istream& operator>>(istream& is, tuple<T1, T2, T3>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t);
}
template <typename T1, typename T2, typename T3, typename T4>
istream& operator>>(istream& is, tuple<T1, T2, T3, T4>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5, T6>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>
         get<5>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6, typename T7>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5, T6, T7>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>
         get<5>(t) >> get<6>(t);
}
template <typename T>
istream& operator>>(istream& is, vector<T>& as) {
  for (int i : range(as.size())) is >> as[i];
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& ss) {
  for (auto a : ss) {
    if (a != ss.begin()) os << " ";
    os << a;
  }
  return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
template <typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& m) {
  bool isF = true;
  for (auto& p : m) {
    if (!isF) os << endl;
    os << p;
    isF = false;
  }
  return os;
}
template <typename T1>
ostream& operator<<(ostream& os, const tuple<T1>& t) {
  return os << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const tuple<T1, T2>& t) {
  return os << get<0>(t) << " " << get<1>(t);
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t);
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5, T6>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t) << " " << get<5>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6, typename T7>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5, T6, T7>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t) << " " << get<5>(t) << " "
            << get<6>(t);
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& as) {
  for (int i : range(as.size())) {
    if (i != 0) os << " ";
    os << as[i];
  }
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& as) {
  for (int i : range(as.size())) {
    if (i != 0) os << endl;
    os << as[i];
  }
  return os;
}
template <typename T>
inline T INF() {
  assert(false);
};
template <>
inline int INF<int>() {
  return 1 << 28;
};
template <>
inline long long INF<long long>() {
  return 1LL << 58;
};
template <>
inline double INF<double>() {
  return 1e16;
};
template <>
inline long double INF<long double>() {
  return 1e16;
};
template <class T>
inline T EPS() {
  assert(false);
};
template <>
inline int EPS<int>() {
  return 1;
};
template <>
inline long long EPS<long long>() {
  return 1LL;
};
template <>
inline double EPS<double>() {
  return 1e-8;
};
template <>
inline long double EPS<long double>() {
  return 1e-8;
};
template <typename T>
T upper_pow2(T n) {
  T res = 1;
  while (res < n) res <<= 1;
  return res;
}
template <typename T>
T msb(T n) {
  int d = 30;
  while ((1 << d) > n) d--;
  return d;
}
template <typename T, typename U>
T pmod(T v, U M) {
  return (v % M + M) % M;
}
template <class Cost>
struct Edge {
  int to;
  Cost cost;
  Edge(int to, Cost cost) : to(to), cost(cost){};
  bool operator<(Edge r) const { return cost < r.cost; }
  bool operator>(Edge r) const { return cost > r.cost; }
};
template <class Cost>
ostream& operator<<(ostream& os, const Edge<Cost>& e) {
  return os << "(->" << e.to << "," << e.cost << ")";
}
template <class Cost>
using Graph = vector<vector<Edge<Cost>>>;
template <class Cost>
class CentroidDecomposition {
 public:
  Graph<Cost>& g;
  vector<int> cdepth, sub;
  vector<vector<int>> ctree;
  CentroidDecomposition(Graph<Cost>& g)
      : g(g), cdepth(g.size(), INF<int>()), sub(g.size()), ctree(g.size()) {
    create_centroid(0, 0);
  }
  int create_centroid(int v, int d) {
    subtree_size(-1, v, d);
    int s = search_centroid(-1, v, sub[v], d).second;
    cdepth[s] = d;
    for (auto& e : g[s])
      if (cdepth[s] < cdepth[e.to])
        ctree[s].push_back(create_centroid(e.to, d + 1));
    return s;
  }
  int subtree_size(int p, int v, int d) {
    int c = 1;
    for (auto& e : g[v])
      if (e.to != p && d < cdepth[e.to]) c += subtree_size(v, e.to, d);
    return sub[v] = c;
  }
  pair<int, int> search_centroid(int p, int v, int tot, int d) {
    pair<int, int> res(1 << 28, -1);
    int cs = 1, m = 0;
    for (auto& e : g[v])
      if (e.to != p && d < cdepth[e.to]) {
        res = min(res, search_centroid(v, e.to, tot, d));
        m = max(m, sub[e.to]);
        cs += sub[e.to];
      }
    m = max(m, tot - cs);
    res = min(res, pair<int, int>(m, v));
    return res;
  }
};
class Main {
 public:
  void run() {
    int N;
    cin >> N;
    Graph<int> g(N);
    for (int i = (int)(0); i < (int)(N - 1); ++i) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      g[u].push_back({v, 1});
      g[v].push_back({u, 1});
    }
    CentroidDecomposition<int> cd(g);
    for (int i = (int)(0); i < (int)(N); ++i)
      if (cd.cdepth[i] > 26) {
        cout << "Impossible!" << endl;
        return;
      }
    vector<char> cs(N);
    for (int i = (int)(0); i < (int)(N); ++i) cs[i] = cd.cdepth[i] + 'A';
    cout << cs << endl;
  }
};
int main() {
  cout << fixed << setprecision(20);
  cin.tie(0);
  ios::sync_with_stdio(false);
  Main().run();
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Now Fox Ciel becomes a commander of Tree Land. Tree Land, like its name said, has n cities connected by n - 1 undirected roads, and for any two cities there always exists a path between them.

Fox Ciel needs to assign an officer to each city. Each officer has a rank — a letter from 'A' to 'Z'. So there will be 26 different ranks, and 'A' is the topmost, so 'Z' is the bottommost.

There are enough officers of each rank. But there is a special rule must obey: if x and y are two distinct cities and their officers have the same rank, then on the simple path between x and y there must be a city z that has an officer with higher rank. The rule guarantee that a communications between same rank officers will be monitored by higher rank officer.

Help Ciel to make a valid plan, and if it's impossible, output "Impossible!".

Input

The first line contains an integer n (2 ≤ n ≤ 105) — the number of cities in Tree Land.

Each of the following n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) — they mean that there will be an undirected road between a and b. Consider all the cities are numbered from 1 to n.

It guaranteed that the given graph will be a tree.

Output

If there is a valid plane, output n space-separated characters in a line — i-th character is the rank of officer in the city with number i. 

Otherwise output "Impossible!".

Examples

Input

4
1 2
1 3
1 4


Output

A B B B


Input

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10


Output

D C B A D C B D C D

Note

In the first example, for any two officers of rank 'B', an officer with rank 'A' will be on the path between them. So it is a valid solution.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class range {
 private:
  struct Iter {
    int v;
    int operator*() { return v; }
    bool operator!=(Iter& itr) { return v < itr.v; }
    void operator++() { ++v; }
  };
  Iter i, n;

 public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iter& begin() { return i; }
  Iter& end() { return n; }
};
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  return is >> p.first >> p.second;
}
template <typename T1>
istream& operator>>(istream& is, tuple<T1>& t) {
  return is >> get<0>(t);
}
template <typename T1, typename T2>
istream& operator>>(istream& is, tuple<T1, T2>& t) {
  return is >> get<0>(t) >> get<1>(t);
}
template <typename T1, typename T2, typename T3>
istream& operator>>(istream& is, tuple<T1, T2, T3>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t);
}
template <typename T1, typename T2, typename T3, typename T4>
istream& operator>>(istream& is, tuple<T1, T2, T3, T4>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5, T6>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>
         get<5>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6, typename T7>
istream& operator>>(istream& is, const tuple<T1, T2, T3, T4, T5, T6, T7>& t) {
  return is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>
         get<5>(t) >> get<6>(t);
}
template <typename T>
istream& operator>>(istream& is, vector<T>& as) {
  for (int i : range(as.size())) is >> as[i];
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& ss) {
  for (auto a : ss) {
    if (a != ss.begin()) os << " ";
    os << a;
  }
  return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
template <typename K, typename V>
ostream& operator<<(ostream& os, const map<K, V>& m) {
  bool isF = true;
  for (auto& p : m) {
    if (!isF) os << endl;
    os << p;
    isF = false;
  }
  return os;
}
template <typename T1>
ostream& operator<<(ostream& os, const tuple<T1>& t) {
  return os << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const tuple<T1, T2>& t) {
  return os << get<0>(t) << " " << get<1>(t);
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t);
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5, T6>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t) << " " << get<5>(t);
}
template <typename T1, typename T2, typename T3, typename T4, typename T5,
          typename T6, typename T7>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4, T5, T6, T7>& t) {
  return os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " "
            << get<3>(t) << " " << get<4>(t) << " " << get<5>(t) << " "
            << get<6>(t);
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& as) {
  for (int i : range(as.size())) {
    if (i != 0) os << " ";
    os << as[i];
  }
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& as) {
  for (int i : range(as.size())) {
    if (i != 0) os << endl;
    os << as[i];
  }
  return os;
}
template <typename T>
inline T INF() {
  assert(false);
};
template <>
inline int INF<int>() {
  return 1 << 28;
};
template <>
inline long long INF<long long>() {
  return 1LL << 58;
};
template <>
inline double INF<double>() {
  return 1e16;
};
template <>
inline long double INF<long double>() {
  return 1e16;
};
template <class T>
inline T EPS() {
  assert(false);
};
template <>
inline int EPS<int>() {
  return 1;
};
template <>
inline long long EPS<long long>() {
  return 1LL;
};
template <>
inline double EPS<double>() {
  return 1e-8;
};
template <>
inline long double EPS<long double>() {
  return 1e-8;
};
template <typename T>
T upper_pow2(T n) {
  T res = 1;
  while (res < n) res <<= 1;
  return res;
}
template <typename T>
T msb(T n) {
  int d = 30;
  while ((1 << d) > n) d--;
  return d;
}
template <typename T, typename U>
T pmod(T v, U M) {
  return (v % M + M) % M;
}
template <class Cost>
struct Edge {
  int to;
  Cost cost;
  Edge(int to, Cost cost) : to(to), cost(cost){};
  bool operator<(Edge r) const { return cost < r.cost; }
  bool operator>(Edge r) const { return cost > r.cost; }
};
template <class Cost>
ostream& operator<<(ostream& os, const Edge<Cost>& e) {
  return os << "(->" << e.to << "," << e.cost << ")";
}
template <class Cost>
using Graph = vector<vector<Edge<Cost>>>;
template <class Cost>
class CentroidDecomposition {
 public:
  Graph<Cost>& g;
  vector<int> cdepth, sub;
  vector<vector<int>> ctree;
  CentroidDecomposition(Graph<Cost>& g)
      : g(g), cdepth(g.size(), INF<int>()), sub(g.size()), ctree(g.size()) {
    create_centroid(0, 0);
  }
  int create_centroid(int v, int d) {
    subtree_size(-1, v, d);
    int s = search_centroid(-1, v, sub[v], d).second;
    cdepth[s] = d;
    for (auto& e : g[s])
      if (cdepth[s] < cdepth[e.to])
        ctree[s].push_back(create_centroid(e.to, d + 1));
    return s;
  }
  int subtree_size(int p, int v, int d) {
    int c = 1;
    for (auto& e : g[v])
      if (e.to != p && d < cdepth[e.to]) c += subtree_size(v, e.to, d);
    return sub[v] = c;
  }
  pair<int, int> search_centroid(int p, int v, int tot, int d) {
    pair<int, int> res(1 << 28, -1);
    int cs = 1, m = 0;
    for (auto& e : g[v])
      if (e.to != p && d < cdepth[e.to]) {
        res = min(res, search_centroid(v, e.to, tot, d));
        m = max(m, sub[e.to]);
        cs += sub[e.to];
      }
    m = max(m, tot - cs);
    res = min(res, pair<int, int>(m, v));
    return res;
  }
};
class Main {
 public:
  void run() {
    int N;
    cin >> N;
    Graph<int> g(N);
    for (int i = (int)(0); i < (int)(N - 1); ++i) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      g[u].push_back({v, 1});
      g[v].push_back({u, 1});
    }
    CentroidDecomposition<int> cd(g);
    for (int i = (int)(0); i < (int)(N); ++i)
      if (cd.cdepth[i] > 26) {
        cout << "Impossible!" << endl;
        return;
      }
    vector<char> cs(N);
    for (int i = (int)(0); i < (int)(N); ++i) cs[i] = cd.cdepth[i] + 'A';
    cout << cs << endl;
  }
};
int main() {
  cout << fixed << setprecision(20);
  cin.tie(0);
  ios::sync_with_stdio(false);
  Main().run();
  return 0;
}

```