P7763 [COCI2016-2017#5] Ronald

#include <bits/stdc++.h>
using namespace std;
int n, m, g[1005][1005], fl, vis[1005], col[1005];
void dfs(int u) {
    //	cout<<"uuu "<<u<<" "<<col[u]<<endl;
    for (int v = 1; v <= n; v++) {
        if (v == u)
            continue;
        //		cout<<"vvv "<<v<<" "<<col[v]<<endl;
        if (g[u][v]) {
            if (vis[v]) {
                if (col[v] != col[u]) {
                    cout << "NE" << endl;
                    fl = 0;
                    exit(0);
                }
            } else {
                col[v] = col[u];
                vis[v] = 1;
                dfs(v);
            }
        } else {
            if (vis[v]) {
                if (col[v] == col[u]) {
                    cout << "NE" << endl;
                    fl = 0;
                    exit(0);
                }
            } else {
                col[v] = col[u] ^ 1;
                vis[v] = 1;
                dfs(v);
            }
        }
    }
    // cout<<"pppp"<<endl;
    // cout<<endl;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = g[y][x] = 1;
    }
    fl = 1;
    vis[1] = col[1] = 1;
    dfs(1);
    if (fl == 1)
        cout << "DA" << endl;
    return 0;
}