Петя нарисовал на бумаге n кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов – красный, синий или зеленый.
Теперь Петя хочет изменить их раскраску. А именно – он хочет перекрасить каждый кружок в некоторый другой цвет так, чтобы никакие два кружка одного цвета не были соединены линией. При этом он хочет обязательно перекрасить каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен исходно, не разрешается.
Помогите Пете решить, в какие цвета следует перекрасить кружки, чтобы выполнялось указанное условие.
В первой строке вводятся два целых числа n и m – количество кружков и количество линий, которые нарисовал Петя, соответственно ( 1
n1 000, 0m20 000).
Следующая строка содержит n символов из множества {'R', 'G', 'B'} – i-й из этих символов означает цвет, в который раскрашен i-й кружок ('R' – красный, 'G' – зеленый, 'B' – синий).
Далее в m строках задается по два целых числа – пары кружков, соединенных отрезками.
Выведите одну строку, состоящую из n символов из множества {'R', 'G', 'B'} – цвета кружков после перекраски. Если решений несколько, выведите любое.
Если решения не существует, выведите слово "Impossible''.
4 5 RRRG 1 3 1 4 3 4 2 4 2 3
GGBR
4 5 RGRR 1 3 1 4 3 4 2 4 2 3
Impossible
Во Флатландии n городов, расположенных в различных точках плоскости. Известно, что никакие три города не лежат на одной прямой.
Правительство решило построить в стране сеть сверхскоростных шоссе. Сеть шоссе должна быть такой, чтобы из любого города можно было проехать в любой другой по построенным шоссе. А в целях экономии средств было решено, что путь, соединяющий любые два города, должен быть единственным. Каждое шоссе представляет собой отрезок, соединяющий некоторую пару городов.
Завод, выполняющий этот госзаказ, подготовил проект сети шоссе. Проект представляет собой описание n - 1 шоссе. Каждое шоссе задается городами, которые оно соединяет. В целях секретности вместо названий городов в проекте были использованы коды – числа от 1 до n.
Однако когда дело дошло до реализации проекта, выяснилось, что документ, в котором было указано соответствие номеров городам, утерян. Поскольку проект приурочен к пятисотлетию культурной столицы Флатландии, переделывать проект полностью оказалось невозможно. Поэтому было решено установить некоторое новое соответствие номеров городам.
При попытке это сделать разработчики проекта столкнулись со следующей проблемой. В соответствии с техническими нормами строительства, недопустимо, чтобы шоссе пересекались вне городов. Поэтому не любое сопоставление номеров городам допустимо. После пары бессонных ночей главный инженер завода решил поручить спасение проекта вам.
Ваша задача – таким образом сопоставить числам от 1 до n города, чтобы после реализации проекта шоссе не пересекались вне городов, которые они соединяют.
В первой строке вводится целое число n – количество городов во Флатландии ( 2n1500).
Далее следует n описаний городов. Описание каждого города состоит из двух строк. Первая строка содержит название города – строку, состоящую из символов с ASCII-кодами от 33 до 127. Названия различных городов не совпадают. Длина названия города не превышает 60 символов. Вторая строка описания города содержит два целых числа x и y – координаты города. Координаты не превышают 104 по абсолютной величине.
Далее следуют n - 1 строк, которые описывают проект строительства сети шоссе в его текущем состоянии. Каждая строка содержит по два целых числа – номера городов, соединенных шоссе в проекте. Никакое шоссе в проекте не соединяет город сам с собой, никакие два города не соединены более, чем одним шоссе.
Выведите n строк, i-я из этих строк должна содержать название города, который следует сопоставить числу i в проекте. Если решений несколько, выведите любое.
Если решения не существует, выведите строку «No solution».
7 Moscow 2 2 St-Petersburg 0 4 Kirov 6 3 Saratov 5 0 Rybinsk 1 1 Petrozavodsk 2 6 Barnaul 10 -1 1 2 2 4 3 5 4 3 4 7 3 6
St-Petersburg Rybinsk Kirov Saratov Moscow Petrozavodsk Barnaul