Лиса Ciel становится командиром Древоземелья. В Древоземелье, как это следует из названия, есть n городов, соединенных n - 1 ненаправленными дорогами, а между любыми двумя городами существует путь по дорогам Древоземелья.
Лиса Ciel должна назначить каждому городу офицера. У каждого офицера есть ранг — буква от 'A' до 'Z'. Таким образом, имеется 26 различных рангов, самый высокий — 'A', самый низкий — 'Z'.
У Ciel имеется достаточно офицеров каждого ранга. Но не все так просто, должно быть выполнено особое условие: если x, y — два различных города и у их офицеров одинаковые ранги, то на простом пути между x и y должен быть город z, имеющий офицера более высокого ранга. Таким образом, общение между офицерами одного ранга будет гарантированно проходить под присмотром офицера более высокого ранга.
Помогите Ciel составить подходящий план назначения офицеров городам. Если это невозможно, выведите «Impossible!».
Выходные данные
Если подходящий план существует, выведите n символов, разделенных пробелами — i-ый символ обозначает ранг офицера в городе i.
В противном случае, выведите «Impossible!».
Примечание
В первом примере для любых двух офицеров ранга 'B', офицер с рангом 'А' будет на пути между ними. То есть, такое решение подходит.