Vương quốc Alpha là một tiểu vương quốc mới được thành lập và đang trên đà phát triển. Quốc vương của họ - Aleck - quyết định chia nhỏ vương quốc thành ~n~ tỉnh thành để dễ dàng kiểm soát hơn. Để tiết kiệm chi phí, nhà vua chỉ cho xây dưng ~n - 1~ con đường kết nối giữa ~2~ tỉnh thành khác nhau, tuy nhiên vẫn phải đảm bảo ~2~ tỉnh thành bất kỳ phải đến được với nhau.

Nhà vua đang gấp rút đề cử ra ~n~ người giám sát, mỗi người sẽ có nhiệm vụ giám sát hoạt động của ~1~ tỉnh thành. Hơn nữa, nhà vua muốn gán cấp bậc của mỗi người giám sát là ~1~ chữ cái từ 'A' đến 'Z' biểu thị cho mức độ quan trọng của tỉnh thành đó. Bậc 'A' là cao nhất, còn bậc 'Z' là thấp nhất.

Việc gán cấp bậc cho mỗi người giám sát còn phải đảm bảo được rằng: Nếu tồn tại ~2~ thành phố có người giám sát là cùng bậc, thì đường đi kết nối giữa ~2~ thành phố đó phải đi qua ít nhất ~1~ thành phố có người giám sát có cấp bậc cao hơn. Điều này cho thấy được tầm quan trọng của những người giám sát bậc cao.

Đề xuất cho nhà vua Aleck ~1~ cách để thực hiện việc đó, hoặc thông báo cho nhà vua biết điều đó là bất khả thi.

Input

Dòng ~1~: Gồm một số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng tỉnh thành của vương quốc Alpha.

~n - 1~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a, b~ ~(1 \le a, b \le n; a \ne b)~ là một con đường ~2~ chiều kết nối giữa ~2~ tỉnh thành ~a~ và ~b~.

Output

Nếu có ~1~ cách thỏa mãn, in ra ~n~ chữ cái in hoa, chữ cái thứ ~i~ đại diện cho cấp bậc của người giám sát cho tỉnh thành ~i~.

Nếu không, in ra 'Impossible!'.

Scoring

Subtask ~1~ ~(30\%~ số điểm~):~ Mỗi tỉnh thành chỉ được kết nối với tối đa ~2~ tỉnh thành khác.

Subtask ~2~:~(30\%~ số điểm~):~ Khoảng cách tối đa giữa ~2~ tỉnh thành bất kỳ không vượt quá ~50~.

Subtask ~3~:~(40\%~ số điểm~):~ Không có điều kiện gì thêm.

Sample Input 1

4
1 2
1 3
1 4

Sample Output 1

A B B B

Sample Input 2

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

Sample Output 2

D C B C A D C B C D