Codeforces Round 300 |
---|
Закончено |
В параллель ZPP Летней Какой-то Школы подали заявки T школьников. Оргкомитет школы может зачислить любое количество из них, но зачислено должно быть не менее t школьников. Зачисленных школьников необходимо разделить на две группы каким-либо образом (возможно, что в одной из групп не окажется школьников!).
Во время смены школьников параллели ZPP будут учить n преподавателей. Из-за особенностей образовательного процесса каждый из преподавателей должен быть приписан к одной из двух групп (возможно, что к какой-то из групп не будет приписан ни один преподаватель!). i-ый из преподавателей согласен работать в группе при условии, что в ней будет не менее li и не более ri школьников (иначе ему будет либо слишком скучно, либо слишком трудно). Кроме этого, некоторые из преподавателей не ладят друг с другом и поэтому не могут работать в одной группе; всего существует m пар конфликтующих преподавателей.
Вам, как завучу Летней Какой-то Школы, досталась нелегкая задача: определить, сколько школьников зачислить в каждую из групп, а также в каких группах будет преподавать каждый из преподавателей.
В первой строке через пробел записано два целых числа t и T (1 ≤ t ≤ T ≤ 109).
Во второй строке через пробел записано два целых числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105).
В i-ой из следующих n строках через пробел записаны целые числа li и ri (0 ≤ li ≤ ri ≤ 109).
В следующих m строках описаны пары конфликтующих преподавателей. В каждой из этих строк через пробел записано по два целых числа — номера преподавателей в паре. Нумерация преподавателей начинается с единицы. Гарантируется, что никакой преподаватель не конфликтует сам с собой, и каждая пара конфликтующих преподавателей присутствует в списке ровно один раз.
Если распределение возможно, в первой строке выведите одно слово «POSSIBLE» (без кавычек). Во второй строке выведите через пробел два целых числа n1 и n2 — количество школьников в первой и второй группе соответственно, при этом должно выполняться ограничение t ≤ n1 + n2 ≤ T. В третьей строке выведите n символов, i-ый из которых равен 1 или 2, если i-ый преподаватель будет приписан к первой или второй группе соответственно. Если существует несколько допустимых распределений школьников и преподавателей по группам, разрешается вывести любое из них.
Если искомого распределения не существует, выведите единственное слово «IMPOSSIBLE» (без кавычек).
10 20
3 0
3 6
4 9
16 25
POSSIBLE
4 16
112
1 10
3 3
0 10
0 10
0 10
1 2
1 3
2 3
IMPOSSIBLE
Название |
---|