题意：
在一个圆上有n个点，m条边将他们相连，问是否有一种连发使没有两条线相交。
分析：
每条线要么在圆内，要么在圆外，2-sat问题。
代码：
//poj 3207
//sep9
#include <iostream>
#include <stack>
using namespace std;
const int maxN=10024;
const int maxM=4200000;
int e,n,m,t,ecnt;
int head[maxN],ins[maxN],low[maxN],dfn[maxN];
int sol[maxN],belong[maxN];
int x[maxN],y[maxN];
stack<int> s;
struct Edge
{int v,next;
}edge[maxM];void addegde(int u,int v)
{edge[e].v=v;edge[e].next=head[u];head[u]=e++;
}void dfs(int x)
{low[x]=dfn[x]=++t; s.push(x);ins[x]=1;for(int i=head[x];i!=-1;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){dfs(v);low[x]=min(low[x],low[v]);}else if(ins[v]==1)low[x]=min(low[x],dfn[v]);} if(dfn[x]==low[x]){++ecnt; int k;do{k=s.top();s.pop();ins[k]=0;belong[k]=ecnt;}while(dfn[k]!=low[k]);}
}
bool two_sat()
{memset(ins,0,sizeof(ins)); memset(dfn,0,sizeof(dfn)); while(!s.empty()) s.pop();int i;t=0,ecnt=0;for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);for(i=1;i<=n;++i)if(belong[i]==belong[i+n])return false;return true;
}int cross(int i,int j)
{if(x[i]<x[j]&&x[j]<y[i])if(y[j]!=x[i]&&y[j]!=y[i])if(!(x[i]<y[j]&&y[j]<y[i]))return 1; if(x[i]<y[j]&&y[j]<y[i])if(x[j]!=x[i]&&x[j]!=y[i])if(!(x[i]<x[j]&&x[j]<y[i]))return 1;return 0;
}
int main()
{int i,j,a,b,c;char op[8];e=0;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(i=1;i<=m;++i){scanf("%d%d",&x[i],&y[i]);if(x[i]>y[i])swap(x[i],y[i]); }for(i=1;i<=m;++i)for(j=1;j<i;++j)if(cross(i,j)){addegde(i,j+m);addegde(i+m,j);addegde(j,i+m);addegde(j+m,i);}n=m; bool ans=two_sat();printf("%s",ans==true?"panda is telling the truth...":"the evil panda is lying again");return 0;
}