Sắp xếp thiết bị mạng

Trong một hệ thống mạng máy tính hiện đại, các máy chủ và thiết bị được kết nối với nhau theo một cấu trúc đặc biệt, tạo thành một mạng lưới dạng cây. Có tổng cộng \(n\) thiết bị, được nối với nhau bằng \(n-1\) sợi cáp. Một nhà quản lý mạng tên là Dũng có nhiệm vụ gán cho mỗi thiết bị một mức ưu tiên.

Mức ưu tiên này được biểu thị bằng một chữ cái từ 'A' đến 'Z', với 'A' là mức ưu tiên cao nhất và 'Z' là thấp nhất. Dũng có thể sử dụng bất kỳ số lượng chữ cái nào cho mỗi mức ưu tiên.

Tuy nhiên, có một quy tắc quan trọng phải tuân thủ để đảm bảo tính ổn định của mạng: Nếu hai thiết bị khác nhau, \(x\) và \(y\), có cùng mức ưu tiên, thì trên đường truyền đơn giản (đường đi ngắn nhất) giữa chúng phải có một thiết bị \(z\) với mức ưu tiên cao hơn. Điều này giúp đảm bảo rằng mọi giao tiếp giữa các thiết bị cùng cấp đều được một thiết bị quan trọng hơn giám sát.

Nhiệm vụ của bạn là giúp Dũng lập một kế hoạch gán mức ưu tiên hợp lệ. Nếu có thể, hãy chỉ ra mức ưu tiên của từng thiết bị. Nếu không, hãy thông báo rằng không có cách nào để thực hiện.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 2 \times 10^5\)), là số thiết bị.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n, a \ne b\)), mô tả một sợi cáp nối giữa thiết bị \(a\) và thiết bị \(b\).

Output

In ra kết quả trên đầu ra chuẩn theo định dạng sau:

• Nếu có một kế hoạch hợp lệ, xuất ra \(n\) ký tự trên một dòng. Ký tự thứ \(i\) là mức ưu tiên của thiết bị \(i\).
• Nếu không thì xuất ra "Impossible!".

Example

5
1 2
1 3
1 4
1 5

ABBBB