题意：给定一个圈，m条边（给定），边可以通过外面连，也可以通过里面连，
问连完这m条边后，是否可以做到边两两不相交
题解：
将连里面和连外面分别当做一种决策（即每条边都是决策点），
如果有两条边相冲突，即如果这两条边都连里面就会导致不合法，那就
x --- > y' , y --- > x',
额。。。那怎么判断不合法？
注意到被边u ---> v（u < v)割成两半的分别是:
u ~ v,其他，
一条边不经过这条边的充要条件是：两个端点都在这条边的同一侧。
也就是要么都属于u ~ v,要么都属于其他。
x = x * 2,表示连里面
x = x ^ 1，表示连外面
连边的时候记得双向建边，不然是不可能有大于1的强联通分量的（因为对于任意x点只有出边，任意x'点只有入边）
找到一组冲突的就连x --- > y', y --- > x'.
表示x连里面，y就要放外面，反之同理
#include<fstream>//文件输入输出
using namespace std;
#define R register int
#define getchar() *o++
#define AC 2200
#define ac 4000100
char READ[],*o=READ;
int n, m, all, tt, cnt;
int low[AC], dfn[AC], belong[AC];
int date[ac], Next[ac], Head[AC], tot;
int s[AC], top;
bool z[AC];
struct node{
int x,y;
}way[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void add(int f,int w)
{
date[++tot] = w, Next[tot] = Head[f], Head[f] = tot;
date[++tot] = f, Next[tot] = Head[w], Head[w] = tot;//反之也成立，所以要加双向边，不然是不可能有几个连一起的
// printf("%d ---> %d\n",f,w);
} inline void upmin(int &a,int b)
{
if(b < a) a = b;
} void pre()
{
n=read(), m=read(), all = n * ;
for(R i=;i<=m;i++)
{
way[i].x = read(), way[i].y = read();
if(way[i].x > way[i].y) swap(way[i].x, way[i].y);
for(R j=;j<i;j++)//防止重边
{
if(way[j].x > way[i].x && way[j].y < way[i].y) continue;
if(way[j].x < way[i].x && way[j].y < way[i].x) continue;
if(way[j].x > way[i].y && way[j].y > way[i].y) continue;
if(way[j].x < way[i].x && way[j].y > way[i].y) continue;//剩下的就都是冲突的
add(i * , (j * ) ^ );
add(j * , (i * ) ^ );
}
}
} void tarjan(int x)
{
int now;
dfn[x] = low[x] = ++tt;
s[++top] = x, z[x] = true;
for(R i = Head[x]; i ; i = Next[i])
{
now = date[i];
if(!dfn[now])
{
tarjan(now);
upmin(low[x], low[now]);
}
else if(z[now])
upmin(low[x], low[now]);
}
int b = ++cnt;
if(dfn[x] == low[x])
{
while(now = s[top--])
{
belong[now] = b;
z[now] = false;
if(now == x) break;
}
}
} void work()
{
for(R i = ; i <= all; i += )
{
if(belong[i] == belong[i ^ ])
{
printf("the evil panda is lying again\n");
return ;
}
}
printf("panda is telling the truth...\n");
} int main()
{
freopen("in.in","r",stdin);
fread(READ, , , stdin);
pre();
for(R i=;i<=all;i++)
if(!dfn[i]) tarjan(i);
work();
fclose(stdin);
return ;
}