特判无解判错了可太艹了，后来删了特判直接过了……
首先我们发现不能有三个及以上的区间两两不交，因此我们可以考虑一种构造方法
首先不考虑(m)对限制，我们记(A=max_{i=1}^ n l_i,B=min_{i=1}^n r_i)，容易发现若(A+Bin [t,T])那么必然是最优的
如果不是的话，我们讨论一下：
- (A+B<t)，我们发现增大(A)一定是最优的
- (A+B>T)，我们发现减少(B)一定是最优的
因此我们现在求出一对(A,B)之后就很好处理了，根据每一个人的区间([l_i,r_i])判断：
- (A ot in [l_i,r_i]and B ot in [l_i,r_i])，此时显然无解
- (Ain [l_i,r_i]and Bin [l_i,r_i])，此时这个人可以随便放，但是具体地还要根据相邻的人来决定
- (Ain [l_i,r_i]or Bin [l_i,r_i])，此时这个人确定了放在哪一组，我们可以根据它的情况来确定相邻的人的选择，或者判断出冲突产生无解
接下来就是个很显然的黑白染色模型了，直接做就好了，复杂度(O(n))
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
struct edge
{
int to,nxt;
}e[N<<1]; int n,m,head[N],cnt,tl,tr,col[N],x,y,A,B; bool vis[N];
struct interval { int l,r; } a[N];
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt;
e[++cnt]=(edge){x,head[y]}; head[y]=cnt;
}
#define to e[i].to
inline bool paint(CI now)
{
vis[now]=1; for (RI i=head[now];i;i=e[i].nxt)
{
if (~col[to]&&col[to]==col[now]) return 0;
if (~col[now]&&!~col[to]) if (col[to]=col[now]^1,!paint(to)) return 0;
}
return 1;
}
#undef to
int main()
{
RI i; for (scanf("%d%d%d%d",&tl,&tr,&n,&m),B=INF,i=1;i<=n;++i)
scanf("%d%d",&a[i].l,&a[i].r),A=max(A,a[i].l),B=min(B,a[i].r),col[i]=-1;
for (i=1;i<=m;++i) scanf("%d%d",&x,&y),addedge(x,y);
if (A+B<tl) A+=tl-(A+B); if (A+B>tr) B-=A+B-tr; if (B<0) return puts("IMPOSSIBLE"),0;
for (i=1;i<=n;++i)
{
if (a[i].l<=A&&A<=a[i].r&&a[i].l<=B&&B<=a[i].r) continue;
if (a[i].l<=A&&A<=a[i].r) col[i]=0; else
if (a[i].l<=B&&B<=a[i].r) col[i]=1; else return puts("IMPOSSIBLE"),0;
}
for (i=1;i<=n;++i) if (!vis[i]&&!paint(i)) return puts("IMPOSSIBLE"),0;
for (i=1;i<=n;++i) if (!~col[i]&&(col[i]=0,!paint(i))) return puts("IMPOSSIBLE"),0;
puts("POSSIBLE"); printf("%d %d
",A,B);
for (i=1;i<=n;++i) putchar(col[i]?'2':'1'); return 0;
}