CF538H Summer Dichotomy

有 $T$ 名学生申请进入 Summer Irrelevant School 的 ZPP 班。校方可以录取任意数量的学生，但至少要录取 $t$ 名学生。被录取的学生需要被分成两组，分组方式任意（可能有一组为空）。 在教学期间，ZPP 班的学生由 $n$ 名老师辅导。由于教育过程的特殊性，每位老师必须被分配到两组中的一组（可能某组没有老师）。第 $i$ 位老师愿意工作的组必须至少有 $l_i$ 名学生，至多有 $r_i$ 名学生（否则要么太无聊，要么太辛苦）。此外，有一些老师互相不喜欢，因此不能被分到同一组，一共有 $m$ 对有冲突的老师。 作为 Summer Irrelevant School 的首席教师，你接到一个艰巨的任务：确定每组应招收多少学生，以及每位老师应被分到哪个组。

第一行包含两个用空格分隔的整数 $t$ 和 $T$（$1 \leq t \leq T \leq 10^{9}$）。 第二行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n \leq 10^{5}$，$0 \leq m \leq 10^{5}$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leq l_i \leq r_i \leq 10^{9}$）。 接下来的 $m$ 行描述有冲突的老师对。每行包含两个用空格分隔的整数，表示有冲突的两位老师的编号。老师编号从 1 开始。保证不存在老师和自己冲突，也不存在重复的有冲突老师对。

如果存在可行分配，第一行输出单词“POSSIBLE”（不带引号）。第二行输出两个用空格分隔的整数 $n_1$ 和 $n_2$，表示第一组与第二组的学生人数，满足 $t \leq n_1 + n_2 \leq T$。第三行输出 $n$ 个字符，第 $i$ 字符为 1 或 2，分别表示第 $i$ 位老师被分到第一组或第二组。如果存在多种可行分配方式，可以任选其一。 如果不存在可行分配方案，输出单词“IMPOSSIBLE”。

由 ChatGPT 5 翻译