CF27D Ring Road 2

好一眼的题，据说出题人给的做法不是2-SAT，因此才会有这样的数据范围，但这个模型yysy实在是太典了啊喂

不难发现每条边的取法就是两种，并且内部和外部的边之间绝对不会相交，因此考虑使用2-SAT模型

枚举两条边\(i,j\)，如果\(i,j\)同时放在一边会产生冲突，就钦定两者的状态必须相异，然后这题就做完了

如果数据范围较大不允许\(O(m^2)\)建图的话会有点麻烦，应该要用数据结构优化下建图啥的

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=205;
int n,m,x[N],y[N],dfn[N],low[N],stk[N],col[N],vis[N],top,idx,scc; vector <int> v[N];
inline void addedge(RI x,CI y)
{
	v[x].push_back(y); v[y].push_back(x);
}
inline void Tarjan(CI now)
{
	dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
	for (int to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
	else if (vis[to]) low[now]=min(low[now],dfn[to]);
	if (low[now]==dfn[now])
	{
		col[now]=++scc; vis[now]=0;
		while (stk[top]!=now) col[stk[top]]=scc,vis[stk[top--]]=0; --top;
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	if (scanf("%d%d",&x[i],&y[i]),x[i]>y[i]) swap(x[i],y[i]);
	auto ID=[&](CI x,CI tp)
	{
		return tp*m+x;
	};
	auto check=[&](CI a,CI b)
	{
		return (x[i]<a&&a<y[i])&&!(x[i]<=b&&b<=y[i]);
	};
	for (i=1;i<=m;++i) for (j=i+1;j<=m;++j)
	if (check(x[j],y[j])||check(y[j],x[j])) addedge(ID(i,1),ID(j,0)),addedge(ID(i,0),ID(j,1));
	for (i=1;i<=2*m;++i) if (!dfn[i]) Tarjan(i);
	for (i=1;i<=m;++i) if (col[ID(i,0)]==col[ID(i,1)]) return puts("Impossible"),0;
	for (i=1;i<=m;++i) putchar(col[ID(i,0)]>col[ID(i,1)]?'i':'o');
	return 0;
}