PartyTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatus

Description
n12n 2n

Input
n n (n<= 1000) m m ( m < (n - 1) * (n -1)) m4 A1,A2,C1,C2 A1,A2 C1,C2 0 1 0 n -1 Output YES NO Sample Input 2 1 0 1 1 1 Sample Output YES

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <algorithm>
 
using namespace std;
 
stack<int> s;
bool vis[20100];
int low[20100];
int degree[20100];
int lastshow[20100];
int dfn[20100];
int cnt;
int n, m;
int Bcnt;
int id;
int index;
bool instack[20100];
int level[20100];
 
void init(){
    for(int i = 0;i <= 2*n+2; i ++){
        low[i] = 0;
        lastshow[i] = -1;
        dfn[i] = 0;
        level[i] = 0;
        instack[i] = false;
    }
    cnt = 0;
    index = 1;
    Bcnt = 0;
    while(!s.empty())
        s.pop();
}
 
struct edge{
    int to;
    int next;
}e[2000010];
 
void insert(int a, int b){
    e[cnt].to = b;
    e[cnt].next = lastshow[a];
    lastshow[a] = cnt++;
}
 
void dfs(int i){
    int j;
    low[i] = dfn[i] = index++;
    instack[i] = true;
    s.push(i);
    id = lastshow[i];
   // printf("x %d", id);
    while(id != -1){
        //printf("x %d", id);
        j = e[id].to;
        if(!dfn[j]){
           // printf("#%d#", dfn[j]);
            dfs(j);
            low[i] = min(low[i], low[j]);
        }
        else if(instack[j])
            low[i] = min(low[i], dfn[j]);
        id = e[id].next;
        //printf("d");
    }
    if(dfn[i] == low[i]){
        Bcnt ++;
        do{
            j = s.top();
            s.pop();
            level[j] = Bcnt;
            instack[j] = false;
        }
        while(j != i);
    }
}
 
bool solve(){
    bool flag = true;
    for(int i = 0; i <= n-1; i ++){
        if(level[2*i] == level[2*i+1]){
            flag = false;
            break;
        }
    }
    return flag;
}
 
int main(){
    int i, a1, a2, c1, c2;
    while(~scanf("%d %d", &n ,&m)){
        init();
        for(i = 1; i <= m; i ++){
            scanf("%d %d %d %d", &a1, &a2, &c1, &c2);
            insert(2 * a1 + c1, 2 * a2 + 1 - c2);
            insert(2 * a2 + c2, 2 * a1 + 1 - c1);
        }
        for(i = 0; i < 2*n; i ++){
            if(0 == dfn[i])
            dfs(i);
        }
//        for(i = 0; i < n; i ++){
//            printf("%d %d %d\n",dfn[i], low[i], level[i]);
//        }
        if(solve())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}