// Author: Klay Thompson
// Problem: P10829 [COTS/CETS 2023] 三元图 Graf
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10829
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D("[Debug] "#__VA_ARGS__ " = "), \
              debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 500010;

int n, m, dfn[maxn], low[maxn], stk[maxn], sz[maxn], mxsz[maxn], vis[maxn], asz, rt, timer, top, tot;
vector<int> e[maxn], g[maxn];

void tarjan(int u) {
  dfn[u] = low[u] = ++timer, stk[++top] = u;
  for (int v : e[u]) {
    if (!dfn[v]) {
      tarjan(v), chkmn(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        tot++;
        g[u].emplace_back(tot);
        g[tot].emplace_back(u);
        while (stk[top] != v) {
          g[stk[top]].emplace_back(tot);
          g[tot].emplace_back(stk[top]);
          top--;
        }
        g[v].emplace_back(tot);
        g[tot].emplace_back(v);
        top--;
      }
    } else {
      chkmn(low[u], dfn[v]);
    }
  }
}

void findrt(int u, int fa) {
  sz[u] = (u <= n), mxsz[u] = 0;
  for (int v : g[u]) {
    if (vis[v] || v == fa) continue;
    findrt(v, u), sz[u] += sz[v];
    chkmx(mxsz[u], sz[v]);
  }
  chkmx(mxsz[u], asz - sz[u]);
  if (mxsz[u] <= asz / 2) rt = u;
}

void dfs(int u, int fa) {
  sz[u] = (u <= n);
  for (int v : g[u]) {
    if (vis[v] || v == fa) continue;
    findrt(v, u), sz[u] += sz[v];
  }
}

void solve(int u, int bsz) {
  if (bsz == 1) return;
  if (bsz % 3 != 0) cout << "ne\n", exit(0);
  vis[u] = 1;
  vector<int> son;
  for (int v : g[u]) {
    if (vis[v]) continue;
    dfs(v, u), son.emplace_back(sz[v]);
  }
  if (SZ(son) != 3 || *max_element(ALL(son)) != bsz / 3) cout << "ne\n", exit(0);
  for (int v : g[u]) {
    if (vis[v]) continue;
    asz = bsz / 3, rt = 0, findrt(v, u), solve(rt, bsz / 3);
  }
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m;
  rep (i, 1, m) {
    int u, v;
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  tot = n, tarjan(1);
  rep (i, 1, n) if (!dfn[i]) cout << "ne\n", exit(0);
  asz = n, rt = 0, findrt(1, 0), solve(rt, n);
  cout << "da\n";
}