/* 2-sat 题意：给定一个圆，圆上一些点。两点一线。现给出一些线，这些线可以在圆内连起来，也可以在圆外。 问有没有可能所有的线画完 且 不出现相交。 思路：把线画在圆内或圆外 看成一个组合。其它的则建边。 */ #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; //typedef __int64 int64; typedef pair PII; #define MP(a,b) make_pair((a),(b)) const int maxn = 2225; const int maxm = 250000; const int inf = 0x7fffffff; const double pi=acos(-1.0); const double eps = 1e-8; struct Edge{ int u,v,next; }edge[ maxm*2+5 ]; int cnt,head[ maxn ]; int vis[ maxn ]; int dfn[ maxn ],low[ maxn ]; int belong[ maxn ],Cnt,id; stacks; struct EDGE{ int l,r; }E[ maxn ]; void init(){ id = Cnt = 0; cnt = 0; while( !s.empty() ) s.pop(); memset( head,-1,sizeof( head ) ); memset( vis,-1,sizeof( vis ) ); memset( dfn,-1,sizeof( dfn ) ); memset( low,-1,sizeof( low ) ); } void addedge( int a,int b ){ edge[ cnt ].u = a; edge[ cnt ].v = b; edge[ cnt ].next = head[ a ]; head[ a ] = cnt++; } bool ok( int L,int R ){ int x1 = E[L].l; int y1 = E[L].r; int x2 = E[R].l; int y2 = E[R].r; if( x2>x1&&x2=y1 ) return true; if( y2<=x1 ) return true; } if( y2>x1&&y2=y1 ) return true; if( x2<=x1 ) return true; } return false; } void tarjan( int cur ){ dfn[ cur ] = low[ cur ] = id++; vis[ cur ] = 1; s.push( cur ); for( int i=head[ cur ];i!=-1;i=edge[i].next ){ int nxt = edge[ i ].v; if( dfn[ nxt ]==-1 ){ tarjan( nxt ); low[ cur ] = min( low[ cur ],low[ nxt ] ); } else if( vis[ nxt ]==1 ){ low[ cur ] = min( low[ cur ],dfn[ nxt ] ); } } if( dfn[ cur ]==low[ cur ] ){ Cnt ++; while( 1 ){ int tmp = s.top(); s.pop(); vis[ tmp ] = 0; belong[ tmp ] = Cnt; if( tmp==cur ) break; } } } int main(){ int n,m; while( scanf("%d%d",&n,&m)==2 ){ init(); int a,b; for( int i=1;i<=m;i++ ){ scanf("%d%d",&a,&b); a++,b++; E[ i ].l = min( a,b ); E[ i ].r = max( a,b ); } for( int i=1;i<=m;i++ ){ for( int j=i+1;j<=m;j++ ){ if( ok( i,j )==true ){ addedge( i,j+m ); addedge( j+m,i ); addedge( i+m,j ); addedge( j,i+m ); } } }//build mat for( int i=1;i<=2*m;i++ ){ if( dfn[i]==-1 ){ tarjan( i ); } } // bool f = true; for( int i=1;i<=m;i++ ){ if( belong[i]==belong[i+m] ){ f = false; break; } } if( f==false ) printf("the evil panda is lying again"); else printf("panda is telling the truth..."); printf("\n"); } return 0; }