The problem can be rephrased as follows.

We have an undirected graph with \(N\) vertices and \(M\) edges.
We construct a graph \(G'\) by the following procedure. Initially, \(G'\) only contains vertices \(1,2,\dots,N\).
For every edge \(u-v\), choose one of the following three to apply it.

• Add a directed edge \(u \rightarrow v\) to \(G'\).
• Add a directed edge \(v \rightarrow u\) to \(G'\).
• In the final graph \(G'\) resulting from applying all the operations, identify \(u\) with \(v\).

There are \(3^M\) ways to choose the operations. How many of them make \(G'\) a DAG (Directed Acyclic Graph)?

We adopt an approach of a bit DP (Dynamic Programming), where vertex sets with indegrees \(0\) are removed incrementally.
However, when a vertex set is removed, if the remaining vertex set contains a vertex with indegree \(0\), they are double-counted. How can we avoid this?

When removing a vertex set, the connected component to be removed must be identified as a connected component (otherwise, one of them has a non-zero indegree.)

Here, consider \(dp[\) Binary representation \(i\) of the surviving vertices \(] =\) \(\{\) the number of possible graphs \(\}\). It is initialized with \(dp[0] = 1\).

If we know \(dp[j]\) for all \(0 \le j < i\), how can we find \(dp[i]\)?

When scanning all subsets \(s\) of \(i\), it is sufficient to apply the inclusion-exclusion principle that transitions as follows:

\(\displaystyle dp[i] = \sum_{s \subset i, s \neq \varnothing} dp[i \setminus s] \times (-1)^{(c(s)+1)}\) (where \(c(s)\) is the number of connected components that \(s\) form in \(G\))

By the inclusion-exclusion principle above, for all integer \(k\), the cases with exactly \(k\) vertices with indegrees \(0\) are (essentially) summed up exactly once.

By precomputing the connected components for all subsets of the vertex set, the problem can be solved in a total of \(O(3^n)\) time.

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;
using pi=pair<int,int>;

#define mod 998244353

int main(){
  int n,m;
  cin >> n >> m;
  vector<pi> eg(m);
  for(auto &nx : eg){
    cin >> nx.first >> nx.second;
    nx.first--;nx.second--;
  }

  vector<int> comp(1<<n);
  for(int i=0;i<(1<<n);i++){
    int res=__builtin_popcount(i);
    dsu uf(n);
    for(auto &nx : eg){
      if((i&(1<<nx.first))==0){continue;}
      if((i&(1<<nx.second))==0){continue;}
      if(!uf.same(nx.first,nx.second)){
        uf.merge(nx.first,nx.second);
        res--;
      }
    }
    comp[i]=res;
  }

  vector<int> dp(1<<n,0);
  dp[0]=1;
  for(int i=1;i<(1<<n);i++){
    for(int j=(1<<n)-1;;j--){
      j&=i;
      if(j==0){break;}
      if(comp[j]%2){
        dp[i]+=dp[i^j];
      }
      else{
        dp[i]+=(mod-dp[i^j]);
      }
      dp[i]%=mod;
    }
  }
  cout << dp[(1<<n)-1] << "\n";
  return 0;
}