题意简述

给一个环和若干线段，要求构造方案使得把线段划分为两个集合使得每个集合的线段都能覆盖整个环。

题解

提供一个线性做法。

我们首先判断是否存在单点被覆盖少于两次，如果存在的话显然无解，判断这个只需要差分就好了。

我们之后把环倍长，按照如下办法建图：

如果一个线段覆盖 $[l,r](l\le r)$ 我们就建一个从 $l$ 到 $r+1$ 的有向边，如果覆盖的是 $[1,r]\cup [l,n](l>r)$ 那么我们就建一个从 $l$ 到 $r+n$ 的有向边（我们称以上建的边为实边或者前向边）。之后若 $i$ 点被线段覆盖了大于 $2$ 次，我们就建 $i+1$ 连向 $i$ 以及一条 $i+n+1$ 连向 $i+n$ 的有向边（我们称这些边为虚边或者反向边）。

之后我们枚举所有点 $i(i\le n)$，搜索是否存在一条 $i$ 到达 $i+n$ 的路径，若存在那么就合法，若不存在就无解。

我们考虑一下这个做法的正确性，若存在一条从 $i$ 到达 $i+n$ 的路径，显然这条路径上的所有实边能够覆盖整个路径，之后我们可以对这个路径做一些精简，扣去路径中被包含的边，使得路径最后大致长成这个样子：

我们发现路径不重叠的部分因为每一个点都被至少两个线段覆盖了，我们把另一个不在路径上的线段分到另外一组，那么这个点仍然在两个组都会被覆盖。至于路径重叠的部分，我们重叠部分肯定要走反向边，然而反向边存在当且仅当被大于 $2$ 条线段覆盖，所以说重叠部分尽管我们花费了两个线段，仍然留存了一个能覆盖重叠部分的线段分到另一个组，所以依然合法。

但是注意一个细节就是可能存在 $F=C+n$ 的情况，那么 $C$ 到 $B$ 的反向边在原来的部分和倍长的部分各走了一遍，也就是说反向边走了两遍可能会存在问题，如果出现这种情况我们发现其实 $A$ 到 $C$ 的边其实没必要取了，我们直接从 $B$ 出发就能到 $B+n$ 其不存在反向边走了两次情况，我们要记着搜完路径把这种情况判掉，把最开头的没有必要的边全删掉。

所以我们只要搜到路径，精简完路径然后踢掉没有必要的开头，实际上这道题的方案就构造完了，精简操作时间复杂度是 $O(n)$ 的，可以参考我的代码。

那么现在我们需要想办法在线性时间复杂度搜到一条合法路径。

我们发现一个关键性质就是假如一个点 $v$ 在 $a$ 搜索路径的时候走过，那么在 $b(b>a)$ 搜索路径的时候肯定不会走 $v$。特别的我们只证明 $b=a+1$ 的情况，别的情况感性理解一下其实也差不多。考虑使用反证法，假如 $b$ 到达 $b+n$ 需要借助 $v$，显然假如存在 $b+n$ 到 $a+n$ 的反向边，那么我们在搜 $a$ 的时候直接借助 $v$ 走到 $b+n$ 再通过反向边到达 $a+n$ 了，我们也就不会搜索 $b$ 了，直接就找到答案了。那么如果不存在 $b+n$ 到 $a+n$ 的反向边呢，假如说 $v$ 不可以到达大于 $a+n$ 的点，那自然也也不能到达 $b+n$，我们不需要考虑 $v$。那我们如果能到达大于 $a+n$ 的点 ，如果不存在反向边使得能够回到 $a+n$，那么一定没有解。 $a$ 能到达大于 $a+n$ 的点，那么 $a$ 显然被覆盖了两次，如果覆盖大于两次，就有反向边了，所以不能再存在任何边跨过了 $a+n$，只有一条边跨过 $a+n$，显然是无解的，因为这条边只能分给一个组，另一个组一定就覆盖不全了，所以如果出现这种情况，都无解了，考不考虑 $v$ 也没有意义了。

所以我们就可以打标记了，搜过的点不重复搜索，这样每个点和边都最多只会走一次，时间复杂度是 $O(n+m)$。

放个代码：

#include<bits/stdc++.h>
#define rv std::views::reverse
#define in :
using namespace std;
using std::ranges::iota_view;
auto range(int end){return iota_view(1,end+1);}
auto range(int start,int end){if(start>end)return range(0);return iota_view(start,end+1);}
const int N=2e5+5;
struct edge{
	int to;
	int nxt;
	int w;
}e[N*2];
int b[N],head[N],tot,vis[N],n,m,des;
int l[N],r[N],ans[N];
deque<int> s;
deque<int> res;
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	e[tot].w=w;
	head[u]=tot;
}
int dfs(int u){
	vis[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
//		cout<<u<<"->"<<v<<" "<<e[i].w<<"\n";
		if(vis[v])continue;
		if(e[i].w) s.push_back(e[i].w);
		if(v==des||dfs(v))return 1;
		if(e[i].w) s.pop_back();
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(auto i in range(m)){
		int lz,rz;
		cin>>lz>>rz;
		l[i]=lz,r[i]=rz;
		if(lz<=rz){
			b[lz]++;
			b[rz+1]--;
			add(lz,rz+1,i);
		}else{
			b[1]++,b[rz+1]--;
			b[lz]++,b[n+1]--;
			add(lz,rz+n+1,i);
		}
	}
	for(auto i in range(n)){
		b[i]+=b[i-1];
		if(b[i]>2){
			add(i+1,i,0);
			if(i!=n)add(i+n+1,i+n,0);
		}
		if(b[i]<2){
			cout<<"impossible\n";
			return 0;
		}
	}
	for(auto i in range(n)){
		des=i+n;
		if(dfs(i)){
			int rx=r[s[0]];
			res.push_back(s[0]);
			for(auto i in range(s.size()-1)){
				if(i<s.size()-1&&l[s[i+1]]<=rx) continue;
				res.push_back(s[i]),rx=r[s[i]];
			}
			rx-=n;
			while(res.size()>=2&&l[res[1]]<=rx)res.pop_front();
			for(auto i in res)ans[i]=1;
			for(auto i in range(m))cout<<ans[i];
			cout<<"\n";
			return 0;
		}
	}
	cout<<"impossible\n";
}