We can split every node p into twonodes: p_in and p_out, then we can constructed a directed bipartite graph.



Source Code
Problem: 3713		User: ikeay
Memory: 908K		Time: 3891MS
Language: G++		Result: Accepted

    Source Code

    #include <assert.h>
    #include <ctype.h>
    #include <float.h>
    #include <limits.h>
    #include <math.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <sys/types.h>

    #include <algorithm>
    #include <complex>
    #include <iostream>
    #include <list>
    #include <map>
    #include <numeric>
    #include <queue>
    #include <set>
    #include <sstream>
    #include <stack>
    #include <string>
    #include <vector>
    using namespace std;

    #define SZ(a) (int)(a).size()
    #define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
    #define REP(i,n) for (int i=0; i<(n); ++i)
    #define ALL(c) c.begin(), c.end()
    #define CLR(c,n) memset(c, n, sizeof(c))
    #define CONTAIN(it, c) (c.find(it) != c.end())
    typedef vector<int> VI;
    typedef pair<int, int> PII;
    typedef long long LL;
    template <class T> void checkmin(T &a, T b) { if (b<a) a=b; }
    template <class T> void checkmax(T &a, T b) { if (b>a) a=b; }

    const int MAXN=512, MAXM=40<<10;
    int n, e, head[MAXN], nextid[MAXM], dest[MAXM], match[MAXN];
    bool matchdst[MAXN], visited[MAXN];

    void add_edge(int src, int dst) {
      dest[e] = dst;
      nextid[e] = head[src];
      head[src] = e;
      ++e;
    }

    bool go(int src, int dst) {
      for (int i = head[src]; i != -1; i = nextid[i]) {
        int next = dest[i];
        if (next == dst) {
          if (matchdst[src]) continue;
          matchdst[src] = true;
          return true;
        }
        if (visited[next]) continue;
        visited[next] = true;
        if (go(match[next], dst)) {
          match[next] = src;
          return true;
        }
      }
      return false;
    }
    bool check(int src, int dst) {
      REP(i, n) match[i] = i;
      CLR(matchdst, 0);
      REP(i, 3) {
        CLR(visited, 0);
        if (!go(src, dst)) return false;
      }
      return true;
    }
    bool go(void) {
      for (int i = 1; i < n; ++i)
        if (!check(0, i) || !check(i, 0))
          return false;
      return true;
    }
    int main(int argc, char *argv[]) {
      int m, a, b;
      while (scanf("%d%d", &n, &m) == 2 && n > 0) {
        CLR(head, -1); e = 0;
        REP(i, n) add_edge(i, i);
        while (m--) scanf("%d%d", &a, &b), add_edge(a, b), add_edge(b, a);
        printf("%s\n", go() ? "YES" : "NO");
      }
    }