挺巧妙的题。
首先可以根据每个点出现时间知道每条边出现时间。然后就是一个 SGT 分治了……吗？发现如果对于每个时刻记录此时有哪些点和 \(1\) 联通，每次都要 \(O(n)\) 的时间扫一遍，这样肯定是不行的。
那么怎么办呢？于是考虑在并查集合并一次的时候判断合并中的两个点中的一个是否与 \(1\) 联通，然后传递答案。
说来简单，但是怎么实现这一过程呢？作者一开始想的是，对于线段树的每一棵子树搜一遍，然后清空。这样做的复杂度似乎是 \(O(n\log^2n)\) 的，但是不太好写。
然后参考题解，学到了一种相当巧妙的做法。就是对于每个点记录当前累计在多少个叶子节点被记录，打上一个标记，每次并查集撤销的时候传递标记，合并的时候取消标记。具体参考代码理解。
code：
点击查看代码
int n,m,k=2e5,top,st[N][2],c[N],pd[N],L[N],R[N];
mt19937 rnd(time(0));
struct DSU{
int fa[N];
int find(int x){return fa[x]?find(fa[x]):x;}
il void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(c[x]<c[y])swap(x,y);
pd[x]-=pd[y];
fa[x]=y,st[++top][0]=x,st[top][1]=y;
}
}D;
struct SGT{
int tot,head[N<<2];
struct node{int u,v,nxt;}e[M];
il void add(int u,int v,int o){e[++tot]={u,v,head[o]},head[o]=tot;}
void update(int l,int r,int o,int x,int y,int u,int v){
if(x>y)return;
if(l>=x&&r<=y)return add(u,v,o);
int mid=(l+r)>>1;
if(x<=mid)update(l,mid,o<<1,x,y,u,v);
if(y>mid)update(mid+1,r,o<<1|1,x,y,u,v);
}
void solve(int l,int r,int o){
int tmp=top;
go(i,o)D.merge(e[i].u,e[i].v);
if(l==r){
pd[D.find(1)]++;
while(top>tmp){
int u=st[top][0],v=st[top--][1];
pd[u]+=pd[v],D.fa[u]=0;
}
return;
}
int mid=(l+r)>>1;
solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
while(top>tmp){
int u=st[top][0],v=st[top--][1];
pd[u]+=pd[v],D.fa[u]=0;
}
}
}T;
void Yorushika(){
scanf("%d%d",&n,&m);
rep(i,1,n)scanf("%d%d",&L[i],&R[i]),c[i]=rnd();
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
T.update(1,k,1,max(L[u],L[v]),min(R[u],R[v]),u,v);
}
T.solve(1,k,1);
rep(i,1,n)if(pd[i])printf("%d ",i);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}