Submission #10387086

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,top,b[N],vis[N],val[N],head[N],fa[N];
struct node{
	int x,y;
}a[N];
struct E{
	int too,next,zh;
}edge[N*2];
vector<int>g;
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int find(int x)
{
	if(fa[x]==x)return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
bool cmp(node a,node b)
{
	return a.x<b.x;
}
void add(int a,int b,int c)
{
	edge[++top].too=b;edge[top].zh=c;
	edge[top].next=head[a];head[a]=top;
}
int dfs(int u)
{
	int res=val[u];
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].too,w=edge[i].zh;
		if(vis[v])continue;
		int x=dfs(v);
		if(x)
		{
			g.push_back(w);
			res^=1;
		}
	}
	return res;
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n+1;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		a[i].x=read();a[i].y=read();
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)b[i]=a[i].x;
	for(int i=1;i<=n;i++)val[i]=a[i].y^a[i-1].y;
	for(int i=1;i<=m;i++)
	{
		int l=read(),r=read();
		l=lower_bound(b+1,b+n+1,l)-b;
		r=upper_bound(b+1,b+n+1,r)-b;
		int x=find(l),y=find(r);
		if(x==y)continue;
		add(l,r,i);
		add(r,l,i);
		fa[x]=y;
	}
	dfs(n+1);
	for(int i=1;i<=n;i++)
	{
		if(vis[i])continue;
		if(dfs(i)==1)
		{
			puts("-1");
			return 0;
		}
	}
	sort(g.begin(),g.end());
	cout<<g.size()<<endl;
	for(int i=0;i<g.size();i++)printf("%lld ",g[i]);
	return 0;
}

Submission Info

Judge Result