SAT-2

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#define clr( x , y ) memset( x ,y , sizeof x )
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define TAM 2010
#define debug( x ) cout << #x << " = " << x << endl
#define f(i,n) for(int i = 0 ; i < n ; i++)
#define ff(i,a,b) for(int i = a ; i < b ; i++)
#define all( x ) x.begin() , x.end()
#define ral( x ) x.rbegin() , x.rend()

using namespace std ;

typedef pair<int,int> ii ;
typedef pair<ii,int> pii ;
typedef long long ll ;
typedef long double ld ;

int n , m ;
vector<int> g1[ TAM ] , g2[ TAM ] ;
stack<int> st ;
int v[ TAM ] ;
int scc[ TAM ] ;
int cmp ;

int neg( int x ){ return (x<<1) + 1 ;}
int pos( int x ){ return (x<<1) ; }

void init(){
    n *= 2 ;
    for(int i = 0 ; i < n ; i++) g1[ i ].clear() , g2[ i ].clear() ;
    clr( scc , -1 ) ;
    cmp = 0 ;
    stack<int> aux ;
    st = aux ;
}

void dfs1( int x ){
    v[ x ] = true ;
    for(int i = 0 ; i < g1[ x ].size() ; i++)
        if( !v[ g1[ x ][ i ] ] )
            dfs1( g1[ x ][ i ] ) ;
    st.push( x ) ;
}

void dfs2( int x ){
    scc[ x ] = cmp ;
    v[ x ] = true ;
    for(int i = 0 ; i < g2[ x ].size() ; i++)
        if( !v[ g2[ x ][ i ] ] )
            dfs2( g2[ x ][ i ] ) ;
}

int main(){

    while( scanf("%d%d" , &n , &m ) == 2 ){
        init() ;
        for(int i = 0 ; i < m ; i++){
            int a , b ;
            scanf("%d%d" , &a , &b ) ;
            if( a > 0 ){
                a-- ;
                if( b > 0 ){
                    b-- ;
                    g1[ neg( a ) ].push_back( pos( b ) ) , g1[ neg( b ) ].push_back( pos( a ) ) ;
                    g2[ pos( b ) ].push_back( neg( a ) ) , g2[ pos( a ) ].push_back( neg( b ) ) ;
                }
                else{
                    b *= -1 ; b-- ;
                    g1[ neg( a ) ].push_back( neg( b ) ) , g1[ pos( b ) ].push_back( pos( a ) ) ;
                    g2[ neg( b ) ].push_back( neg( a ) ) , g2[ pos( a ) ].push_back( pos( b ) ) ;
                }
            }else{
                a *= -1 ; a-- ;
                if( b > 0 ){
                    b-- ;
                    g1[ pos( a ) ].push_back( pos( b ) ) , g1[ neg( b ) ].push_back( neg( a ) ) ;
                    g2[ pos( b ) ].push_back( pos( a ) ) , g2[ neg( a ) ].push_back( neg( b ) ) ;
                }
                else{
                    b *= -1 ; b-- ;
                    g1[ pos( a ) ].push_back( neg( b ) ) , g1[ pos( b ) ].push_back( neg( a ) ) ;
                    g2[ neg( b ) ].push_back( pos( a ) ) , g2[ neg( a ) ].push_back( pos( b ) ) ;
                }
            }
        }
        clr( v , 0 ) ;
        for(int i = 0 ; i < n ; i++) if( !v[ i ] ) dfs1( i ) ;
        clr( v , 0 ) ;

        while( !st.empty() ){
            int node = st.top() ; st.pop() ;
            if( scc[ node ] == -1 ) dfs2( node ) , cmp++ ;
        }

        bool resp = false ;
        n /= 2 ;
        for(int i = 0 ; i < n ; i++) resp |= ( scc[ pos( i ) ] == scc[ neg( i ) ] ) ;
//      for(int i = 0 ; i < n ; i++) cout << scc[ i ] << ' ' ; cout << endl ;
        cout << !resp << endl ;

    }
    return 0 ;
}