题意
有$n$个要求，要求电台$x_i$与$y_i$中至少选择$1$个
共$p$个电台，满足一个电台的信号功率范围为$[l_i,r_i]$
在$[1,M]$选择一个信号功率，要求满足选择的所有电台
有$m$对电台不能同时选择
判断是否能够满足，如果是，输出方案
数据范围：$2 \le n,p,M,m \le 4 \cdot 10^5$
题解
对于至少选择一个和不能同时选择的要求，我们容易看出这是一个$2-SAT$问题
用节点$x_i$表示选择电台$x_i$，用节点$x_i+p$表示不选择$x_i$
则要求从$x_i$与$y_i$中至少选择$1$个可以拆解为不选择$y_i \rightarrow$选择$x_i$ 与 不选择$x_i \rightarrow$选择$y_i$
建边$$y_i+p \rightarrow x_i$$$$x_i+p \rightarrow y_i$$
相似的，不能同时选择可以拆解为选择$x_i \rightarrow$不选择$y_i$ 与 选择$y_i \rightarrow$不选择$x_i$
建边$$x_i \rightarrow y_i+p$$$$y_i \rightarrow x_i+p$$
现在还需要解决信号功率的限制，选择一个电台后我们无法得知一个确定的信号功率来约束它，但我们知道哪些信号功率不能选，因此由$i$向$[1,l_i-1] \cup [r_i+1,M]$对应的节点建边，并且由$[l_i,r_i]$对应的节点向$i+p$建边，意为不选择此段范围中的信号功率便不能选择$i$
但是如果这样建边的话空间时间都承受不了，考虑将建边的对象转化为区间，能不能向区间的两端建边表示对这段区间的选择与否呢？这样是可以的，由$i$向信号频率为$x$对应的节点建边，表示不能选择小于$x$的信号频率，可是如果我们要表示不能选择大于$x$的信号频率呢？再额外使用$M$个节点保存大于的信息就好了
而要保存区间连续的关系，还需在区间中向相邻的值建边，如下
tot=p<<1;
pre[1]=++tot;
suc[1]=tot+M;
for(int i=2;i<=M;i++){
pre[i]=++tot;
suc[i]=tot+M;
add(pre[i],pre[i-1]);
add(suc[i-1],suc[i]);
}至此，约束条件已经被全部写入图中，跑一次$Tarjan$即可得知是否存在方案，而输出答案，只需取满足条件的$max(l_i)$作为最后选定的信号功率（因为题目未作额外要求）
代码：
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int N=4e5+10;
stack<int> S;
int n,p,M,m,x,y;
int l[N],r[N];
int cnt,tot,dep,cc,ans;
int head[N<<2],pre[N],suc[N],dfn[N<<2],low[N<<2],clr[N<<2],a[N];
struct edge{
int nxt,to;
} e[N*10];
template <typename T>
inline T Max(T a,T b){
return a>b?a:b;
}
template <typename T>
inline T Min(T a,T b){
return a<b?a:b;
}
inline void add(int u,int v){
e[++cnt]=(edge){head[u],v};
head[u]=cnt;
}
void Tarjan(int u){
dfn[u]=low[u]=++dep;
S.push(u);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=Min(low[u],low[v]);
}
else if(!clr[v])
low[u]=Min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
cc++;
for(int t;t!=u;){
t=S.top();
S.pop();
clr[t]=cc;
}
}
}
int main(){
scanf("%d%d%d%d",&n,&p,&M,&m);
tot=p<<1;
pre[1]=++tot;
suc[1]=tot+M;
for(int i=2;i<=M;i++){
pre[i]=++tot;
suc[i]=tot+M;
add(pre[i],pre[i-1]);
add(suc[i-1],suc[i]);
}
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
add(x+p,y);
add(y+p,x);
}
for(int i=1;i<=p;i++){
scanf("%d%d",&l[i],&r[i]);
if(l[i]-1>=1)
add(i,pre[l[i]-1]);
if(r[i]+1<=M)
add(i,suc[r[i]+1]);
add(suc[l[i]],i+p);
add(pre[r[i]],i+p);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y+p);
add(y,x+p);
}
for(int i=1;i<=(p<<1);i++)
if(!dfn[i])
Tarjan(i);
for(int i=1;i<=p;i++)
if(clr[i]==clr[i+p]){
puts("-1");
return 0;
}
for(int i=1;i<=p;i++)
if(clr[i]<clr[i+p]){
ans=Max(ans,l[i]);
a[++*a]=i;
}
printf("%d %d\n",*a,ans);
for(int i=1;i<=*a;i++)
printf("%d ",a[i]);
return 0;
}