飞机票： http://poj.org/problem?id=3207

分析：题目有点难懂。。。但还是2-sat 。。题目的意思就是按顺时针给定圆上n个点。标号0~n-1.然后m个连接。。。注意：连接可以连接在圆内也可以在圆外。。。这里提示我们不一定是直线。。。然后判断是否可以不相交在圆内或圆外。。可以相交在圆上。。。

题目都看晕了。。。其实很简单。。。假如当前是的i个连接且坐标为li ri,如果有个连接k。且lk>li&&lk<ri&&rk>ri 或则

rk>li&&rk<lr&&lk<li 这样就代表这两条不能在一侧。否则相交。。画个图你就懂了

这里有个判断我很喜欢

  int cnt=0;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
  if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;

如果cnt=1就相交。。。为什么呢cnt=1时就说明前面满足了一个条件。另一个不满足。。就是说只有一个点在里面。另个在外面。。怎么画肯定都相交。。。简单易懂。。然后就是2-sat 啪啪啪~~~oh，no！好像还有个问题。。就是这里要添加4条边。。因为互相制约。。然后就可以AC啦

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=1234;
vector<int> V[maxn];
int n,m;
struct he
{
    int l,r;
} JLJ[567];
void init()
{
    for(int i=0; i<=2*m; i++)V[i].clear();
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        if(u>v)swap(u,v);
        JLJ[i].l=u;
        JLJ[i].r=v;
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=i+1; j<=m; j++)
        {
            int cnt=0;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].l<JLJ[j].r))cnt++;
            if((JLJ[i].l>JLJ[j].l&&JLJ[i].r<JLJ[j].r))cnt++;
            if(cnt==1)
            {
                int u=2*(i-1);
                int v=2*(j-1);
                V[u].push_back(v+1);
                V[u+1].push_back(v);
                V[v].push_back(u+1);
                V[v+1].push_back(u);
            }
        }
    }
}
bool instack[maxn];
int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum;
void tarjan(int u)
{
    dfn[u]=low[u]=indexx++;
    instack[u]=1;
    sta[++scnt]=u;
    for(int i=0; i<V[u].size(); i++)
    {

        int v=V[u][i];
        if(dfn[v]==-1)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])low[u]=min(dfn[v],low[u]);
    }
    if(dfn[u]==low[u])
    {
        for(int v=-1; v!=u; scnt--)
        {
            v=sta[scnt];
            instack[v]=0;
            belong[v]=cntnum;
        }
        cntnum++;
    }
}
void play()
{
    indexx=cntnum=0;
    scnt=-1;
    memset(dfn,-1,sizeof(dfn));
    memset(instack,0,sizeof(instack));
    for(int i=0; i<2*m; i++)
    {
        if(dfn[i]==-1)tarjan(i);
    }
    for(int i=0; i<m; i++)
    {
        if(belong[i*2]==belong[i*2+1])
        {
            printf("the evil panda is lying again\n");
            return;
        }
    }
    printf("panda is telling the truth...\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
    //  cout << "Hello world!" << endl;
    return 0;
}