题意分析

liympanda 在圆的边界上放置了 $n$ 个点（编号 $0$ 到 $n-1$），并要连接其中的 $m$ 对点。每条连接线可以完全放在圆内或完全放在圆外，但要求：

• 圆内 的连线不能相交（除端点外）。
• 圆外 的连线不能相交（除端点外）。

我们需要判断是否存在一种布线方式，使得所有连线在圆内或圆外都不相交。

解题思路

这个问题可以转化为图的二部性问题，即判断是否存在一种方式，将所有的连线分成“圆内”和“圆外”两组，使得同一组内的连线不会交叉。

关键观察

• 两条连线 $(a_i, b_i)$ 和 $(a_j, b_j)$ 在圆内相交，当且仅当它们在圆上的顺序是交错的，即 $a_i < a_j < b_i < b_j$（假设 $a_i < b_i$ 且 $a_j < b_j$）。
• 如果两条连线在圆内相交，那么它们不能同时放在圆内，必须有一条放在圆外，反之亦然。

建模方法

1. 冲突检测：遍历所有连线对 $(i, j)$，检查它们是否在圆内相交。如果相交，则它们不能放在同一侧（圆内或圆外）。
2. 构建冲突图：将每条连线视为一个节点，如果两条连线在圆内相交，则在它们之间建立一条边，表示它们必须放在不同的组。
3. 二分图判定：使用**二分图染色（BFS/DFS）**判断该冲突图是否可以二染色（即是否可以将连线分成两组，使得同一组内没有冲突）。

算法选择

• 时间复杂度：$O(m^2)$（检测所有连线对是否相交） + $O(m + E)$（二分图判定，其中 $E$ 是冲突边数）。
• 空间复杂度：$O(m^2)$（存储冲突关系）。

标程

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=1100;
int n,m,top;
bool mark[2*N];
int stack[2*N];
vector<int> g[2*N];
struct Node
{
	int a,b;
}edges[N];
bool cmp(Node x,Node y)
{
	return x.a<y.a;
}
void init()
{
	memset(mark,false,sizeof(mark));
	for(int i=0;i<2*N;i++)
	{
		g[i].clear();
	}
}
void addedge(int x,int idx,int y,int idy)
{
	x=2*x+idx;
	y=2*y+idy;
	g[x].push_back(y);
}
bool dfs(int x)
{
	if(mark[x^1]) return false;
	if(mark[x]) return true;
	mark[x]=true;
	stack[++top]=x;
	int len=g[x].size();
	for(int i=0;i<len;i++)
	{
		if(!dfs(g[x][i])) return false;
	}
	return true;
}
bool twosat()
{
	for(int i=0;i<2*n;i+=2)
	{
		if(!mark[i]&&!mark[i+1])
		{
			top=0;
			if(!dfs(i))
			{
				while(top>0)
					mark[stack[top--]]=false;
				if(!dfs(i+1)) return false;
			}
		}
	}
	return true;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(int i=0;i<m;i++)
		{
			scanf("%d%d",&edges[i].a,&edges[i].b);
			if(edges[i].a>edges[i].b)
			{
				int tmp=edges[i].a;
				edges[i].a=edges[i].b;
				edges[i].b=tmp;
			}
		}
		sort(edges,edges+m,cmp);
		for(int i=0;i<m;i++)
		{
			for(int j=i+1;j<m;j++)
			{
				if(edges[j].b>edges[i].b&&edges[i].b>edges[j].a)
				{
					addedge(i,0,j,1);
					addedge(i,1,j,0);
					addedge(j,0,i,1);
					addedge(j,1,i,0);
				}
			}
		}
		if(twosat()) printf("panda is telling the truth...\n");
		else printf("the evil panda is lying again\n");
	}
	return 0;
}