题意
- 有一些同学和(n)个老师，要求从中选出至少(t)个至多(T)学生分成两组
- 要求第(i)名老师所分得的学生人数在([l_i, r_i])的范围内并且每个老师都要分到某一组去
- 并且有一些老师不能在同一组
- 构造一组方案
先不考虑(t, T)的限制，那么分情况考虑：
- 所有区间都有交集
- 最后答案将老师分成两个集合，且两集合交集的交集为空
对于情况1，只要在交集里面选两个点就好
对于情况2，考虑选的较小的那个点(x)，可以发现这个点一定会在所有(r_i)的前面，否则另外一个点更大，那这个(r_i)就无法分组了，所以这个点一定会满足：
[xleqmin_{i=1}^{n}{r_i}
]
再考虑较大的那个点(y)，同样的，这个点一定会所有(l_i)的后面，否则同样不满足题意，即：
[ygeqmax_{i=1}^n{l_i}
]
然后再考虑(t,T)的限制，同样有两种情况：
- (x+y<t)，由于(x)只能减小，所以只能增大(y)，但增大多可能会不满足区间的限制，所以尽量让(y)更小
- (x+y>T)，同理只能最小地减小(x)
于是，我们能得到的最终的(x,y)一定能满足题意，否则就无解，之后建出二分图跑跑就好了
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 100000
using namespace std;
int T, t, n, m, mn = inf, mx = 0, L[maxn + 5], R[maxn + 5], col[maxn + 5];
template <class T>
void read(T &x){
char ch;
bool ok;
for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
if(ok) x = -x;
}
int fa[2 * maxn + 5], to[maxn + 5];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
int main(){
//freopen("in", "r", stdin);
read(t); read(T); read(n); read(m);
For(i, 1, n){
read(L[i]); read(R[i]);
mn = min(mn, R[i]);
mx = max(mx, L[i]);
}
if(mn + mx < t) mx = t - mn;
if(mn + mx > T) mn = T - mx;
if(mn + mx < t || mn + mx > T || mn < 0){puts("IMPOSSIBLE"); return 0;};
For(i, 1, 2 * n) fa[i] = i;
For(i, 1, m){
int u, v; read(u); read(v);
if(find(u) == find(v)){puts("IMPOSSIBLE"); return 0;}
fa[find(n + u)] = find(v);
fa[find(n + v)] = find(u);
}
For(i, 1, n) if(find(n + i) != n + i) to[find(n + i)] = find(i);
For(i, 1, n) L[find(i)] = max(L[find(i)], L[i]), R[find(i)] = min(R[find(i)], R[i]);
For(i, 1, n) if(find(i) == i){
if(L[i] > R[i]){puts("IMPOSSIBLE"); return 0;}
if(!to[i]){
//cout << L[i] << " " << R[i] << endl;
if(mn >= L[i] && mn <= R[i]) col[i] = 1;
else if(mx >= L[i] && mx <= R[i]) col[i] = 2;
else{puts("IMPOSSIBLE"); return 0;}
}
else{
if(mn >= L[i] && mn <= R[i] && mx >= L[to[i]] && mx <= R[to[i]]){
col[i] = 1;
col[to[i]] = 2;
}
else if(mn >= L[to[i]] && mn <= R[to[i]] && mx >= L[i] && mx <= R[i]){
col[i] = 2;
col[to[i]] = 1;
}
else{puts("IMPOSSIBLE"); return 0;}
}
}
puts("POSSIBLE");
printf("%d %d
", mn, mx);
For(i, 1, n) printf("%d", col[find(i)]);
return 0;
}