Solution Notes (Neal Wu): Let us say that an edge points to a vertex if that vertex was responsible for building the edge. We would like to know how many assignments there are such that each edge points to some vertex, and each vertex has at most one edge pointing to it.

Our first observation is that we can solve the problem for each connected component and then multiply the answers together since the components are independent. Now let us assume a connected component has n vertices. We have three different cases for the number of edges:

• The component has n - 1 edges. Then it is a tree, and only one vertex will not have any edge pointing to it. However this vertex can be any of the vertices; to see this, root the tree at the vertex. Then every edge must point down toward its child. Thus the number of assignments is n.
• The component has n edges. Then it takes the form of a cycle (of at least two vertices) where each cycle vertex is the root of a tree. In this case every edge within a tree must point down toward its child, whereas the cycle edges can point two different ways--clockwise or counterclockwise. Thus the number of assignments is 2.
• The component has more than n edges. Then the answer is 0 since some vertex will have more than one edge pointing to it. However due to the wording of the problem, the contest directors decided not to include any such test cases in the final data set.

Our solution is simply a DFS to find and categorize each connected component, as in the below implementation from problem author Mark Gordon:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

#define MOD 1000000007
#define MAXM 100000

bool vis[MAXM];
vector<int> E[MAXM];

pair<int, int> dfs(int x) {
  if(vis[x]) return make_pair(0, 0);
  vis[x] = true;

  pair<int, int> ret(1, E[x].size());
  for(int i = 0; i < E[x].size(); i++) {
    pair<int, int> res = dfs(E[x][i]);
    ret.first += res.first;
    ret.second += res.second;
  }
  return ret;
}

int main() {
  freopen("alliance.in", "r", stdin);
  freopen("alliance.out", "w", stdout);
  int N, M;
  cin >> N >> M;

  for(int i = 0; i < M; i++) {
    int u, v; cin >> u >> v; u--; v--;
    E[u].push_back(v);
    E[v].push_back(u);
  }

  int result = 1;
  for(int i = 0; i < N; i++) {
    if(vis[i] || E[i].empty()) continue;

    pair<int, int> res = dfs(i);
    if(res.second % 2) cerr << "PROBLEM" << endl;
    res.second /= 2;
    if(res.first == res.second + 1) {
      result = (1ll * result * res.first) % MOD;
    } else if(res.first == res.second) {
      result = (2 * result) % MOD;
    } else {
      result = 0;
    }
  }

  cout << result << endl;
}