Problem:
 Score : 300 points    Problem Statement You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges. Here, a self-loop is an edge where a_i = b_i (1≤i≤M) , and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M) . How many different paths start from vertex 1 and visit all the vertices exactly once? Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph   The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition   However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition   Neither the following path shown in Figure 4, because it does not start from vertex 1 .    Figure 4: another example of a path that does not satisfy the condition       Constraints  2≦N≦8   0≦M≦N(N-1)/2   1≦a_i<b_i≦N   The given graph contains neither self-loops nor double edges.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the number of the different paths that start from vertex 1 and visit all the vertices exactly once.        Sample Input 1 3 3
1 2
1 3
2 3      Sample Output 1 2  The given graph is shown in the following figure:     The following two paths satisfy the condition:          Sample Input 2 7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7      Sample Output 2 1  This test case is the same as the one described in the problem statement.

Solution (Python):
import itertools

n, m = map(int, input().split())


path=[[False]* n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0

for i in itertools.permutations(list(range(n))):
	
	if i[0]==0:
		
		for j in range(n):
			
			if j == n-1:
				ans+=1
				break
			
			if not path[i[j]][i[j + 1]]:
				break
print(ans)

Solution (Python):
import copy


def dfs(i, path, reached, n):
    if reached[i]:
        return n
    reached[i] = True

    if all(reached):
        n += 1
        return n

    for p in path[i]:
        org_reached = copy.deepcopy(reached)
        n = dfs(p, path, org_reached, n)

    return n


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    path = [[] for _ in range(N)]

    for a, b in AB:
        a -= 1
        b -= 1
        path[a].append(b)
        path[b].append(a)

    reached = [False for _ in range(N)]
    n = 0

    n = dfs(0, path, reached, n)
    print(n)


main()

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
path = [[False] * N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    path[a][b] = path[b][a] = True

    ans = 0
    for i in permutations(range(N), N):
        if i[0] == 0:
            for j in range(N):
                if j == N - 1:
                    ans += 1
                    break
                if not path[i[j]][i[j + 1]]:
                    break

print(ans)

Solution (Python):
import sys


def dfs(A: list):
    if len(A) == n:
        for i in range(len(A)-1):
            if A[i+1] not in node[A[i]]:
                break
            if i == n-2:
                ans[0] += 1
        return
    for v in range(2, n+1):
        if v not in A:
            A.append(v)
            dfs(A)
            A.pop()


n, m = map(int, input().split())
node = [set() for _ in range(n+1)]
for x in sys.stdin.readlines():
    a, b = map(int, x.split())
    node[a].add(b)
    node[b].add(a)
ans = [0]
dfs([1])
print(ans[0])

Solution (Python):
import itertools
n,m=map(int,input().split())
edge=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)
ans=0
for junretu in list(itertools.permutations(list(range(2,n+1)))):
  now=1
  flag=True
  for i in list(junretu):
    if not(i in edge[now]):
      flag=False
      break
    now=i
  if flag:
    ans+=1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges=[]
for i in range(M):
    edges.append(list(map(int,input().split())))

res=0
for i in itertools.permutations(range(2,N+1),N-1):
    path=[1]+list(i)
    check=[sorted(path[i:i+2]) in edges for i in range(len(path)-1)]
    if not False in check:
        res+=1
print(res)

Solution (Python):




import sys
from io import StringIO
import unittest
import itertools


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3
1 2
1 3
2 3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7"""
        output = """1"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    P = [list(map(int, input().split())) for _ in range(M)]

    R = itertools.permutations(range(1, N+1))

    ans = 0
    for r in R:
        flag = True
        r = list(r)
        if r[0] != 1:
            break
        for i in range(1, N):
            for p in P:
                if (r[i-1] == p[0] and r[i] == p[1]) or (r[i-1] == p[1] and r[i] == p[0]):
                    break
            else:
                flag = False
        if flag == True:
            ans += 1

    print(ans)


if __name__ == "__main__":
    
    resolve()

Solution (Python):
from networkx import *
N,M = map(int,input().split())
A = [list(map(int,input().split())) for m in range(M)]
G = Graph(A)
ans = 0

for n in range(2,N+1):
  for p in all_simple_paths(G,1,n):
    if len(p)==N:
      ans+=1

print(ans)

Solution (Python):
N, M = map(int, input().split())
to = [[] for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

ans = 0
v = [0] * N

def DFS(n):
    global ans
    v[n] = 1
    
    if sum(v) == N:
        ans += 1
    for i in to[n]:
        if v[i] == 0:
            DFS(i)
    v[n] = 0

DFS(0)
print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())
routes = list(itertools.permutations([i for i in range(2,n+1)]))
nodes = {}
ans = 0
for i in range(1,n+1):
    nodes[i] = []
for _ in range(m):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
for i in range(len(routes)):
    jud = 1
    if routes[i][0] not in nodes[1]:
        jud = 0
    for j in range(n-2):
        if routes[i][j+1] not in nodes[routes[i][j]]:
            jud = 0
    ans += jud
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
edge =[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  edge[a].append(b)
  edge[b].append(a)

all_lis = list(itertools.permutations(list(range(2,n+1))))

def sati(x):
  
  now=1
  for i in range(n-1):
    if not (x[i] in edge[now]):
      return 0
    now=x[i]
  return 1
ans=0
for i in all_lis:
  ans+=sati(i)
print(ans)

Solution (Python):
N,M = map(int,input().split())
G = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
cnt = [0]
def dfs(V,s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1
    else:
        for adj in G[s]:
            if V[adj] == 0:
                dfs(V[:adj] + [1] + V[adj + 1:], adj)
dfs([0] * N,0)
print(cnt[0])

Solution (Python):
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
es = [[0]*N for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a][b] = es[b][a] = 1

ans = 0
import itertools
for ptn in itertools.permutations(range(1,N)):
    ptn = list(ptn)
    for a,b in zip([0]+ptn, ptn):
        if not es[a][b]: break
    else:
        ans += 1
print(ans)

Solution (Python):
from collections import deque

n,m = map(int, input().split())
g = [[] for _ in range(n)]
prev = [0] * n

for i in range(m):
    a,b = map(int, input().split())
    g[a-1].append(b)
    g[b-1].append(a)

count = 0
prev[0] = 1

def keiro(pre,q,now):
    global count
    if len(q) == 0:
            return

    now = q.popleft()
    
    for no in g[now-1]:
        if pre[no-1] == 0:

            pre_1 = pre.copy()
            pre_1[no-1] = 1
            if sum(pre_1) == n:
                count+=1
                return
            q.append(no)
            keiro(pre_1,q,no)
        else:

            keiro(pre,q,no)


keiro(prev,deque([1]),1)
print(count)

Solution (Python):
n,m=list(map(int,input().split()))

es=[[0 for i in range(n)] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  es[a-1][b-1]=1
  es[b-1][a-1]=1


import sys
sys.setrecursionlimit(10**7)




visited=[0 for i in range(n)]
check=[1 for i in range(n)]

def dfs(v,visited):
  
  ans=0
  
  visited[v-1]=1

  if visited==check:
    visited[v-1]=0
    return 1
  
  for i in range(n):
    
    if es[v-1][i]==1 and visited[i]==0:
        ans+=dfs(i+1,visited)
  
  visited[v-1]=0
  return ans

print(dfs(1,visited))

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n,m = LI()
    root = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        root[a].append(b)
        root[b].append(a)

    pers = itertools.permutations(list(range(2,n+1)))
    ans = 0

    for per in pers:
        for i in range(n-1):
            if i == 0:
                now = 1
                next = per[0]
                if next not in root[now]:
                    break
            else:
                now = per[i-1]
                next = per[i]
                if next not in root[now]:
                    break
        else:
            ans += 1
    
    print(ans)
main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)

def main():
    N, M = map(int, input().split())
    repn = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        repn[a - 1].append(b - 1)
        repn[b - 1].append(a - 1)

    visited = [0] * N
    visited[0] = 1
    ans = [0]

    def stroke(u):
        
        if visited == [1] * N:
            ans[0] += 1
            return
        for v in repn[u]:
            if visited[v] == 1: continue
            visited[v] = 1
            stroke(v)
            visited[v] = 0

    stroke(0)
    print(ans[0])

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

n, m = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    i -= 1
    j -= 1
    tree[i].append(j)
    tree[j].append(i)


from collections import deque


first = [True] * n
first[0] = False
todo = deque([(0, first)])
ans = 0
while len(todo) > 0:
    now, history = todo.popleft()
    if not any(history):
        ans += 1
        continue
    for i in tree[now]:
        if history[i]:
            next_history = history.copy()
            next_history[i] = False
            todo.append((i, next_history))

print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[[0]*n for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    l[a-1][b-1]=1
    l[b-1][a-1]=1
d=[int(i)+1 for i in range(n)]
ans=chk=0
for i in list(itertools.permutations(d,n)):
    chk=1
    if i[0]!=1: continue
    for j in range(n-1):
        chk*=l[i[j+1]-1][i[j]-1]
    ans+=chk
print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
m = [set() for _ in range(27)]
for a, b in AB:
    m[a].add(b)
    m[b].add(a)

def main():
    ans = []
    def traverse(n, visits):
        visits = visits | set([n])
        if len(visits) == N:
            ans.append(1)
            return
        for c in m[n] - visits:
            traverse(c, visits)
    traverse(1, set())
    return len(ans)

print(main())

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)

dp = [[0]*n for i in range(2**n)]
dp[1][0] = 1

for s in range(2**n):
    for v in range(n):
        if (s >> v) & 1:
            
            t = s ^ (1 << v)
            for u in g[v]:
                if (t >> u) & 1:
                    dp[s][v] += dp[t][u]

ans = 0
for v in range(n):
    ans += dp[-1][v]
print(ans)

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)

dp = [[0]*n for i in range(2**n)]
dp[1][0] = 1

for s in range(2**n):
    for v in range(n):
        if (s >> v) & 1:
            
            t = s ^ (1 << v)
            for u in g[v]:
                if (t >> u) & 1:
                    dp[s][v] += dp[t][u]

ans = 0
for v in range(n):
    ans += dp[-1][v]
print(ans)

Solution (Python):
import itertools


def main():
    N, M = map(int, input().split())
    node_lst = [x for x in range(N)]
    edge_lst = [list(map(int, input().split())) for _ in range(M)]
    ans = 0

    for route in itertools.permutations(node_lst):
        is_visited = [False] * N
        is_visited[0] = True
        if route[0] != 0:
            continue

        for i in range(N - 1):
            if [route[i] + 1, route[i + 1] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True
            if [route[i + 1] + 1, route[i] + 1] in edge_lst and is_visited[route[i + 1]] == False:
                is_visited[route[i + 1]] = True

        if is_visited == [True] * N:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
import math
N,M = (int(T) for T in input().split())
List = [[] for TM in range(0,M)]
for TM in range(0,M):
    List[TM] = [int(T) for T in input().split()]
    
Node = [[] for TN in range(0,N+1)]
for TM in range(0,M):
    Node[List[TM][0]].append(List[TM][1])
    Node[List[TM][1]].append(List[TM][0])
    
Count = math.factorial(N-1)
for TI in itertools.permutations(range(2,N+1)):
    Root = (1,)+TI
    for TR in range(0,N-1):
        if Root[TR+1] not in Node[Root[TR]]:
            Count -= 1
            break
print(Count)

Solution (Python):
def DFS(num):
    global ans,color
    color[num]="black"
    if "white" not in color[1:]:
        ans +=1
    for i in MAP[num]:
        if color[i]=="white":
            DFS(i)
    color[num]="white"


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

MAP=[[] for _ in range(n+1)]
for a,b in AB:
    MAP[a].append(b)
    MAP[b].append(a)

color=["white" for _ in range(n+1)]
ans=0
DFS(1)
print(ans)

Solution (Python):
from itertools import permutations
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]
MAP=[[] for _ in range(n)]
for a,b in AB:
    MAP[a-1].append(b-1)
    MAP[b-1].append(a-1)

ans=0
for A in permutations(range(n),n):
    if A[0]==0:
        for i in range(n):
            if i==n-1:
                ans +=1
                break
            if A[i+1] not in MAP[A[i]]:break
print(ans)

Solution (Python):
n,m=list(map(int,input().split()))

import sys
sys.setrecursionlimit(10**7)


es=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

  


def dfs(v,visited):
  ans=0
  
  
  visited[v-1]=1
 
  
  if visited==check:
    visited[v-1]=0
    return 1
  
  
  for i in range(n):
    
    if visited[i]==0 and es[v-1][i]==1:
      ans=ans+dfs(i+1,visited)
  
  visited[v-1]=0
   
  return ans





visited=[0 for i in range(n)]
check=[1 for i in range(n)]
print(dfs(1,visited))

Solution (Python):
n,m=map(int, input().split())
alist=[]
for i in range(m):
  a,b=map(int, input().split())
  alist.append([a,b])
  alist.append([b,a])
ans=0
import itertools
t=[i for i in range(1,n+1)]
blist=list(itertools.permutations(t,n))
ans=0
for i in blist:
  flag=True
  for j in range(n-1):
    if [i[j],i[j+1]] not in alist:
      flag=False
  if i[0]!=1:
      flag=False
  if flag:
    ans+=1
print(ans)

Solution (Python):
n,m=map(int, input().split())
alist=[]
for i in range(m):
  a,b=map(int, input().split())
  alist.append([a,b])
  alist.append([b,a])
ans=0
import itertools
t=[i for i in range(1,n+1)]
blist=list(itertools.permutations(t,n))
ans=0
for i in blist:
  flag=True
  for j in range(n-1):
    if [i[j],i[j+1]] not in alist:
      flag=False
    if i[0]!=1:
      flag=False
  if flag:
    ans+=1
print(ans)

Solution (Python):

n,m=list(map(int,input().split()))

es=[[0]*n for i in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1


from itertools import permutations
per=[i+1 for i in range(n-1)]
per=list(permutations(per,n-1))


ans=0
for i in per:
  cnt=0
  if es[0][i[0]]==0:
    continue
  else:
    for j in range(1,n-1):
      if es[i[j]][i[j-1]]==0:
        cnt+=1
    if cnt==0:
      ans=ans+1
print(ans)

Solution (Python):
N,M = map(int,input().split())

line = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    line[a-1].append(b-1)
    line[b-1].append(a-1)

check = [False] * N

def dfs(now):
    global cnt
    global ans
    if cnt == N:
        ans += 1
    else:
        for i in line[now]:
            if check[i] == False:
                check[i] = True
                cnt += 1
                dfs(i)
                check[i] = False
                cnt -= 1

check[0] = True
cnt = 1
ans = 0
dfs(0)
print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

N,M=LI()
graph=[[False]*8 for _ in range(8)]

for _ in range(M):
  a,b=LI()
  a-=1
  b-=1
  graph[a][b]=True
  graph[b][a]=True

def dfs(v,visited):
  all_visited=True
  for i in range(N):
    if not visited[i]:
      all_visited=False
  if all_visited:
    return 1

  ret=0
  for i in range(N):
    if not graph[v][i]:
      continue
    if visited[i]:
      continue
    visited[i]=True
    ret+=dfs(i,visited)
    visited[i]=False

  return ret

visited=[False]*N
visited[0]=True
print(dfs(0,visited))

Solution (Python):
from itertools import permutations
from collections import deque

def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    cnt = 0
    for patterns in permutations(range(1,N)):
        pattern = [0] + list(patterns)
        Q = deque(pattern)
        while Q:
            s = Q.popleft()
            if Q[0] in edge[s]:
                if len(Q) == 1:
                    Q.popleft()
                    break
                else:
                    continue
            else:
                break
        if not Q:
            cnt += 1
    
    print(cnt)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n_ver, n_edge = map(int,input().split())
ad_ls = [[] for _ in range(n_ver)]
for i in range(n_edge):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ad_ls[a].append(b)
    ad_ls[b].append(a)
done_ls = [0] * n_ver
def dfs(ver):
    done_ls[ver] = 1
    num = 0
    if done_ls == [1] * n_ver:
        done_ls[ver] = 0
        return 1
    for nex in ad_ls[ver]:
        if done_ls[nex]:
            continue
        num += dfs(nex)
    done_ls[ver] = 0
    return num
print(dfs(0))

Solution (Python):
n,m=map(int,input().split())

li = [[0]*n for _ in range(n)]


for i in range(m):
    a,b=map(int,input().split())
    li[a-1][b-1]=1
    li[b-1][a-1]=1
  

def dfs(v,used):
    if not False in used:
        return 1


    ans=0
    for i in range(n):
        if not li[v][i]:
            continue
        elif used[i]:
            continue

        else:
            used[i]=True
            ans+=dfs(i,used)
            used[i]=False

    return ans

used=[False]*n
used[0]=True
print(dfs(0,used))

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    ans = [0]
    visited = [False] * N
    def dfs(c, depth):
        visited[c] = True
        if depth == N - 1:
            ans[0] += 1
        else:
            for n in G[c]:
                if not visited[n]:
                    dfs(n, depth + 1)
                    visited[n] = False

    dfs(0, 0)

    print(ans[0])

if __name__ == '__main__':
    resolve()

Solution (Python):
from networkx import *
n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
g = Graph(a)
ans = 0
for i in range(2, n + 1):
  for p in all_simple_paths(g, 1, i):
    if len(p) == n:
      ans += 1
print(ans)

Solution (Python):
n,m = map(int, input().split())
edge = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


import itertools
l = []
for i in range(1,n):
    l.append(i)
llist = list(itertools.permutations(l))


ans = 0
for i in range(len(llist)):
    x = [0] + list(llist[i])
    tnp = 0
    for j in range(n-1):
        if not x[j+1] in edge[x[j]]:
            tnp += 1
            break
    if (tnp==0):
        ans += 1
print(ans)

Solution (Python):
import itertools

n, m = map(int, input().split())
h = [[0]*n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    h[a-1][b-1] = 1
    h[b-1][a-1] = 1

ans = 0
x = list(itertools.permutations(range(1, n+1)))
for i in range(len(x)):
    if x[i][0] == 1:
        for j in range(n-1):
            if h[x[i][j]-1][x[i][j+1]-1] == 0:
                break
        else:
            ans += 1
print(ans)

Solution (Python):
import itertools

n, m = map(int, input().split())
h = [[0]*n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    h[a-1][b-1] = 1
    h[b-1][a-1] = 1

ans = 0
x = list(itertools.permutations(range(1, n+1)))
for i in range(len(x)):
    flag = False
    if x[i][0] == 1:
        flag = True
        for j in range(n-1):
            if h[x[i][j]-1][x[i][j+1]-1] == 0:
                flag = False
                break
    if flag:
        ans += 1
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
query = [[] for _ in range(N)]
for _ in range(M):
    a, b = mapint()
    query[a-1].append(b-1)
    query[b-1].append(a-1)

dp = [[0]*N for _ in range(1<<N)]
dp[1][0] = 1
for i in range(1<<N):
    for j in range(N):
        
        for nx in query[j]:
            if not (i>>nx)&1:
                dp[i+(1<<nx)][nx] += dp[i][j]

print(sum(dp[-1]))

Solution (Python):
import itertools

n, m = map(int, input().split())
p = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1][b-1] = 1
    p[b-1][a-1] = 1

c = list(itertools.permutations(range(n)))
cnt = 0
for i in range(len(c)):
    if c[i][0] == 0:
        for j in range(n-1):
            if p[c[i][j]][c[i][j+1]] != 1:
                break
        else:
            cnt += 1
print(cnt)

Solution (Python):
from itertools import permutations
n_ver,n_edge = map(int,input().split())
path_mat = [[0]*n_ver for _ in range(n_ver)]
for i in range(n_edge):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path_mat[a][b] = 1
    path_mat[b][a] = 1
ans = 0
vers = [i for i in range(n_ver)]
for path in permutations(vers):
    if path[0] != 0:
        continue
    can = True
    for i in range(n_ver-1):
        from_ = path[i]
        to = path[i+1]
        if not path_mat[from_][to]:
            can = False
            break
    if can:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

n, m = map(int, input().split())

edges = {tuple(sorted(map(int, input().split()))) for _ in range(m)}
ans = 0

for i in permutations(range(2,n+1), n-1):
    l = [1] + list(i)
    tmp = sum(1 for edge in zip(l, l[1:]) if tuple(sorted(edge)) in edges) == n-1
    ans += tmp
print(ans)

Solution (Python):
def dfs(parent, connect, passed, N): 
    cnt = 0
    passed.append(parent) 
    if len(passed) == N: 
        cnt = 1
    for next_ in connect[parent]:
        if next_ in passed:
            continue
        cnt += dfs(next_, connect, passed, N) 
    passed.pop() 
    return cnt    

N, M = map(int, input().split())
connect = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = dfs(0, connect, [], N) 
print(ans)

Solution (Python):
def dfs(parent, connect, passed, N):
    cnt = 0
    passed.append(parent)
    if len(passed) == N:
        cnt = 1
    for next_ in connect[parent]:
        if next_ in passed:
            continue
        cnt += dfs(next_, connect, passed, N)
    passed.pop()
    return cnt    

N, M = map(int, input().split())
connect = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
ans = dfs(0, connect, [], N)
print(ans)

Solution (Python):
import sys
from itertools import permutations

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    edge = set()
    for _ in range(m):
        a, b = map(int, input().split())
        edge.add((a - 1, b - 1))
        edge.add((b - 1, a - 1))

    res = 0
    for pattern in permutations(range(n)):
        if pattern[0] == 0:
            for i in range(1, n):
                prev = pattern[i - 1]
                now = pattern[i]
                if (prev, now) not in edge:
                    break
            else:
                res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
N, M = map(int, input().split())
A = []

import itertools
import numpy as np
import collections


Dist = np.array([[0]*N]*N)

for i in range (0, M):
	B, C = map(int, input().split())
	Dist[B-1][C-1] = 1
	Dist[C-1][B-1] = 1

V = collections.deque(itertools.permutations(range(0, N), N))

count = 0

while V:
	P = V.popleft()
	if P[0] == 0:
		d = 0
		for i in range (1, N):
			if Dist[P[i]][P[i-1]] == 1:
				d+=1
			else:
				break
		if d == N-1:
			count+=1
	else:
		continue        

print(count)

Solution (Python):
from itertools import permutations
n, m = map(int,input().split())
p =  [[0] * n for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    p[a-1][b-1] = 1
    p[b-1][a-1] = 1


l = []
for i in permutations(range(1, n), n-1):
    l.append([0] + list(i))


ans= 0
for i in range(len(l)):
    k = l[i]
    for j in range(n-1):
        if p[k[j]][k[j+1]] != 1:
            break
    else:
        ans += 1

print(ans)

Solution (Python):

import itertools
N, M = map(int, input().split())
edges = [input().replace(" ", "") for i in range(M)]
res = 0
for l in itertools.permutations(list(range(1,N+1,1))):
    if l[0]!=1:
        continue
    for i in range(len(l)-1):
        e = str(min(l[i], l[i+1])) + str(max(l[i], l[i+1]))
        if not e in edges:
            break
    else:
        res += 1
print(res)

Solution (Python):
from itertools import permutations as per
n,m = map(int,input().split())
g = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
ans = 0

for l in per(range(n)):
    if l[0] != 0:
        continue
    flag = 1
    for i in range(n-1):
        if l[i+1] not in g[l[i]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

N,M = map(int,input().split())
masu = [[0]*N for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    masu[a][b] = 1
    masu[b][a] = 1
ans = 0
for i in permutations(range(N)):
    if i[0] != 0:continue
    for j in range(N):
        if j==N-1:
            ans += 1
            break
        if not masu[i[j]][i[j+1]]:
            break
print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
edge = [[0 for _ in range(n)] for _ in range(n)]
e = [[int(i)-1 for i in input().split()]for _ in range(m)]
for ei in e:
    i, j = ei
    edge[i][j] = 1
    edge[j][i] = 1

paths = itertools.permutations([i for i in range(n)], n)
ok = 0
for path in paths:
    if path[0] != 0:
        continue
    flag = True
    for ei in range(len(path)-1):
        if edge[path[ei]][path[ei+1]] == 0:
            flag = False
        if flag is False:
            break
    if flag:
        ok += 1
print(ok)

Solution (Python):
import itertools

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

c = [i for i in range(2, n + 1)]
b = []
for x in itertools.permutations(c):
  b.append([1] + list(x))
  
cnt = 0
for x in b:
  exist = True
  for i in range(n-1):
    if not sorted(x[i:i+2]) in a:
      exist = False
      break
  if exist:
    cnt += 1

print(cnt)

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    ab = [NLI() for _ in range(M)]
    
    l = [n for n in range(2,N+1)]
    
    per_list = list(itertools.permutations(l))
    ans = 0
    for p in range(len(per_list)):
        ls_p = list(per_list[p])
        ls_p.insert(0,1)
        
        flg = True
        for n in range(N-1):
            if not [min(ls_p[n],ls_p[n+1]),max(ls_p[n],ls_p[n+1])] in ab:
                flg = False
                continue
        else:
            if flg == True:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()