#include <bits/stdc++.h>

using namespace std;

const int N = 100005, mod = 1e6 + 3;
int n, m;
int dfn[N], low[N], tot;
int st[N], top;
int fac[N], ifac[N], val[N];
pair<int, int> g[N];
vector<int> to[N];
vector<vector<int>> son[N];

int power(int a, int n) {
  int tp = 1;
  while (n) {
    if (n & 1) {
      tp = 1ll * tp * a % mod;
    }
    a = 1ll * a * a % mod, n >>= 1;
  }
  return tp;
}

void dfs1(int i, int fa) {
  low[i] = dfn[i] = ++tot;
  st[++top] = i;

  for (int j : to[i]) {
    if (j == fa) {
      continue;
    }
    if (dfn[j]) {
      low[i] = min(low[i], dfn[j]);
    } else {
      dfs1(j, i);
      low[i] = min(low[i], low[j]);

      if (low[j] < dfn[i]) {
        continue;
      }

      vector<int> tp;
      int x;
      do {
        x = st[top--];
        tp.push_back(x);
      } while (x != j);
      son[i].push_back(tp);
    }
  }
}

int calc(int a, int b) {
  int ans = 0;
  for (int i = b; i != -1; i--) {
    ans = (mod - ans + 1ll * ifac[i] * ifac[b - i] % mod * val[a + 2 * (b - i)]) % mod;
  }
  return 1ll * ans * fac[b] % mod;
}

pair<int, int> dfs2(vector<int> c) {
  static int gu[N], vv1[N];
  int vv = 1;
  for (int x : c) {
    vector<pair<int, int>> tp;
    int s1 = 0;
    for (vector<int> a : son[x]) {
      auto [v0, v1] = dfs2(a);
      if (v1 == -1) {
        vv = 1ll * vv * v0 % mod;
        s1++;
      } else {
        if (v1) {
          tp.emplace_back(v0, v1);
        } else {
          vv = 1ll * vv * v0 % mod;
        }
      }
    }

    int cnt = 0;
    gu[0] = 1;
    for (auto [x, y] : tp) {
      cnt++;
      gu[cnt] = 1ll * gu[cnt - 1] * y % mod;
      for (int j = cnt - 1; j; j--) {
        gu[j] = (1ll * gu[j] * x + 1ll * gu[j - 1] * y) % mod;
      }
      gu[0] = 1ll * gu[0] * x % mod;
    }

    int a = s1;
    for (int j = 0; j <= cnt; j++) {
      vv1[j] = calc(a, j);
    }

    if (a % 2 == 0) {
      for (int j = 0; j <= cnt; j++) {
        g[x].first = (g[x].first + 1ll * gu[j] * vv1[j]) % mod;
      }
      for (int j = 1; j <= cnt; j++) {
        g[x].second = (g[x].second + 1ll * j * vv1[j - 1] % mod * gu[j] + 2ll * a * j % mod * vv1[j - 1] % mod * gu[j]) % mod;
      }
      if (a >= 2) {
        for (int j = 0; j <= cnt; j++) {
          g[x].second = (g[x].second + 1ll * a * (a - 1) / 2 % mod * calc(a - 2, j) % mod * gu[j]) % mod;
        }
      }
      for (int j = 2; j <= cnt; j++) {
        g[x].second = (g[x].second + 2ll * j * (j - 1) % mod * gu[j] % mod * calc(a + 2, j - 2)) % mod;
      }
    } else {
      for (int j = 0; j <= cnt; j++) {
        g[x].first = (g[x].first + 1ll * gu[j] * vv1[j]) % mod;
      }
      g[x].second = -1;
    }
  }

  if (c.size() == 1) {
    int x = c[0];
    if (x == 1) {
      if (g[x].second == -1) {
        cout << 0 << endl;
      } else {
        cout << 1ll * g[x].first * vv % mod;
      }
      exit(0);
    }
    if (g[x].second == -1) {
      g[x].first = 1ll * g[x].first * vv % mod;
      return {g[x].first, 0};
    }
    g[x].first = 1ll * g[x].first * vv % mod;
    return {g[x].first, -1};
  }

  int x = c[0];
  int dd[2][2] = {{0, 0}, {0, 0}};
  if (g[x].second == -1) {
    dd[1][0] = dd[0][1] = 1ll * vv * g[x].first % mod;
  } else {
    dd[0][0] = 1ll * vv * g[x].first % mod;
    dd[1][1] = (1ll * vv * g[x].first + 2ll * vv * g[x].second) % mod;
  }

  for (int j = 1; j != (int)c.size(); j++) {
    int y = c[j];
    for (bool o : {0, 1}) {
      if (g[y].second == -1) {
        dd[o][0] = 1ll * dd[o][0] * g[y].first % mod;
        dd[o][1] = 1ll * dd[o][1] * g[y].first % mod;
      } else {
        int xx = dd[o][0], yy = dd[o][1];
        dd[o][0] = 1ll * yy * g[y].first % mod;
        dd[o][1] = (1ll * xx * g[y].first + 2ll * xx * g[y].second) % mod;
      }
    }
  }

  if (dd[0][0] || dd[1][1]) {
    return {(dd[1][1] + dd[0][0]) % mod, dd[0][0]};
  } else {
    return {(dd[0][1] + dd[1][0]) % mod, -1};
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  cin >> n >> m;
  fac[0] = 1;
  for (int i = 1; i <= m; i++) {
    fac[i] = 1ll * fac[i - 1] * i % mod;
  }
  ifac[m] = power(fac[m], mod - 2);
  for (int i = m - 1; i != -1; i--) {
    ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
  }
  val[0] = 1;
  for (int i = 2; i <= m; i += 2) {
    val[i] = 1ll * (i - 1) * val[i - 2] % mod;
  }
  for (int i = 1; i <= m; i += 2) {
    val[i] = 1ll * i * val[i - 1] % mod;
  }

  while (m--) {
    int x, y;
    cin >> x >> y;
    to[x].push_back(y), to[y].push_back(x);
  }

  dfs1(1, 0);
  dfs2(vector<int>{1});
}