← 返回题目列表

Codeforces · 538/H

H. 夏季二分法

中文机器翻译题面 查看原题

T同学申请进入暑期无关学校ZPP班。学校组委会可以招收任意数量的学生,但至少必须招收t名学生。已报名的学生无论以何种方式均应分成两组(有可能其中一组是空的!)

在轮班期间,ZPP 年级的学生由 n 位老师辅导。由于教育过程的性质,每位教师都应被分配到两个组中的一组(有可能没有教师被分配到某些组!)。第i个老师愿意在一个小组中工作,只要这个小组至少有li个学生,最多有ri个学生(否则要么太无聊,要么太难)。此外,有些教师对彼此不喜欢,因此不能在同一组工作;总共有 m 对冲突的教师。

作为暑期无关学校的班主任,您面临着一项艰巨的任务:确定每个小组招收多少学生以及每个老师在哪个小组授课。

输入

第一行包含两个以空格分隔的整数 t 和 T (1 ≤ t ≤ T ≤ 109)。

第二行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105)。

接下来 n 行的第 i 行包含整数 li 和 ri (0 ≤ li ≤ ri ≤ 109)。

接下来的 m 行描述了一对相互冲突的教师。每行都包含两个以空格分隔的整数——该对中教师的索引。教师的索引从 1 开始。保证没有老师与自己发生冲突,并且没有冲突的老师在列表中出现超过一次。

输出

如果可以进行分发,请在第一行打印一个单词“POSSIBLE”(不带引号)。在第二行中,打印两个空格分隔的整数 n1 和 n2 — 第一组和第二组中的学生人数,相应地,应满足约束 t ≤ n1 + n2 ≤ T。第三行打印n个字符,其中第i个字符应该是1或2,如果第i个老师应该分配到第一组或第二组,则相应地。如果学生和教师分组有多种可能的分布,您可以打印其中任何一个。

如果所寻求的分布不存在,则打印一个单词“IMPOSSIBLE”(不带引号)。

示例

输入 #1

10 20
3 0
3 6
4 9
16 25

输出 #1

POSSIBLE
4 16
112

输入 #2

1 10
3 3
0 10
0 10
0 10
1 2
1 3
2 3

输出 #2

IMPOSSIBLE