Программирование — работа в Москве

Язык программирования: C++ Для себя Решить две задачи на перебор умный перебор. Объяснить алгоритм и асимптотику. Дан неориентированный граф без петель, но, возможно, с кратными рёбрами. Проверьте, существует ли в этом графе независимое множество заданного размера. Формат ввода В первой строке содержатся целые числа V и S — количество вершин в графе и размер искомого независимого множества (1 <= V <= 50, 1 <= S <= 50). Вторая строка содержит целое число E — количество рёбер в графе (0 <= E <= 1000). В каждой из следующих E строк содержится пара вершин bi, ei, описывающая очередное ребро (1 <= bi <= V, 1 <= ei <= V, bi != ei). Формат вывода Выведите YES, если в заданном графе существует независимое множество размера S. В противном случае выведите NO. Петя нарисовал на бумаге n кружков и соединил некоторые пары кружков линиями. После этого он раскрасил каждый кружок в один из трех цветов — красный, синий или зеленый. Теперь Петя хочет изменить их раскраску. А именно — он хочет перекрасить каждый кружок в некоторый другой цвет так, чтобы никакие два кружка одного цвета не были соединены линией. При этом он хочет обязательно перекрасить каждый кружок, а перекрашивать кружок в тот же цвет, в который он был раскрашен исходно, не разрешается. Помогите Пете решить, в какие цвета следует перекрасить кружки, чтобы выполнялось указанное условие. Формат ввода Первая строка содержит два целых числа n и m — количество кружков и количество линий, которые нарисовал Петя, соответственно (1 <= n <= 1 000, 0 <= m <= 20 000). Следующая строка содержит n символов из множества {‘R’, ‘G’, ‘B’} — i-й из этих символов означает цвет, в который раскрашен i-й кружок (‘R’ — красный, ‘G’ — зеленый, ‘B’ — синий). Следующие m строк содержат по два целых числа — пары кружков, соединенных отрезками. Формат вывода Выведите одну строку, состоящую из n символов из множества {‘R’, ‘G’, ‘B’} — цвета кружков после перекраски. Если решений несколько, выведите любое. Если решения не существует, выведите слово «Impossible».