1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define cl(a,b) memset(a,b,sizeof(a)) 5 #define debug(a) cerr<<#a<<"=="<<a<<endl 6 using namespace std; 7 typedef long long ll; 8  9 const int maxn=500*500+10;10 11 int x[500+10],y[500+10];12 int tot,head[maxn];13 bool vis[maxn];14 int s[maxn],top;15 16 struct Edge17 {18     int to,next;19 } edge[maxn];20 21 void init()22 {23     tot=0;24     cl(head,-1);25     cl(vis,false);26 }27 28 void addedge(int u,int v)29 {30     edge[tot].to=v;31     edge[tot].next=head[u];32     head[u]=tot++;33 }34 35 bool dfs(int u)36 {37     if(vis[u^1]) return false;38     if(vis[u]) return true;39     vis[u]=true;40     s[top++]=u;41     for(int i=head[u]; i!=-1; i=edge[i].next)42     {43         if(!dfs(edge[i].to))44         {45             return false;46         }47     }48     return true;49 }50 51 bool Two_sat(int n)52 {53     for(int i=0; i<2*n; i+=2)54     {55         if((vis[i])||(vis[i+1])) continue;56         top=0;57         if(!dfs(i))58         {59             while(top) vis[s[--top]]=false;60             if(!dfs(i^1)) return false;61         }62     }63     return true;64 }65 66 int main()67 {68     int n,m;69     scanf("%d%d",&n,&m);70     init();71     for(int i=0;i<m;i++)72     {73         scanf("%d%d",&x[i],&y[i]);74         if(x[i]>y[i]) swap(x[i],y[i]);75     }76     for(int i=0;i<m;i++)77     {78         for(int j=i+1;j<=m;j++)79         {80             if((x[i]<x[j])&&(y[i]<y[j])&&(y[i]>x[j]))81             {82                 addedge(i*2,j*2+1);83                 addedge(j*2,i*2+1);84                 addedge(i*2+1,j*2);85                 addedge(j*2+1,i*2);86             }87         }88     }89     if(Two_sat(m)) puts("panda is telling the truth...");90     else puts("the evil panda is lying again");91     return 0;92 }/*93 94 4 295 0 196 3 297 98 */