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 sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""





co = 0



n,k = m()

dp = [[0 for i in range(n)] for j in range(n)]

for i in range(k):
    a,b = m()
    a -= 1
    b -= 1
    dp[a][b] = 1
    dp[b][a] = 1

def dfs(now,li,dp):
    global co

    for i in range(n):
        if dp[now][i] == 1 and li[i] == 0:
            po = copy.deepcopy(li)
            po[i] = 1
            dfs(i,po,dp)
    if sum(li) == n:
        co += 1
nnn = [0 for i in range(n)]
nnn[0] = 1
dfs(0,nnn,dp)
print(co)

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
graph = []
for i in range(M):
    a, b = map(int, input().split())
    graph.append(set((a, b)))

g = permutations(range(1, N + 1))

count = 0
for order in g:
    flag = True
    for i in range(N-1):
        if set((order[i], order[i + 1])) not in graph or order[0] != 1:
            flag = False
            break
    if flag:
        count += 1

print(count)

Solution (Python):
from itertools import  permutations

N,M = map(int,input().split())
d = [list(map(int,input().split())) for i in range(M)]

A = []
for i in range(2,N+1):
    A.append(i)

def f(m,n):  
    if m > n:
        l = m
        m = n
        n = l
    for i in range(M):
        if d[i][0] == m and d[i][1] == n:
            return 1
    else:
        return 0

ans = 0
for i in permutations(A,N-1):
    for j in range(N-1):
        if j == 0:
            if f(1,i[0]) == 1:
                continue
            else:
                break
        else:
            if f(i[j-1],i[j]) == 1:
                continue
            else:
                break
    else:
        ans += 1

print(ans)

Solution (Python):


from itertools import permutations


def main():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: (x[0], x[1]))

    result = 0
    P = permutations(range(2, N + 1), N - 1)

    for i in P:
        li = [1] + list(i)
        if sum(list(sorted(edge)) in AB for edge in zip(li, li[1:])) == N - 1:
            result += 1
    print(result)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

ans = 0


def dfs(cnt, current, path):
    if cnt == N:
        global ans
        ans += 1
        
        return
    for i in range(N):
        
        if s[current-1][i] == 1 and i+1 not in path:
            
            
            path.append(i+1)
            dfs(cnt+1, i+1, path)
            for i in range(cnt, len(path)):
                path.pop()


N, M = [int(x) for x in stdin.readline().rstrip().split()]
s = [[0 for i in range(N)] for j in range(N)]
cnt = 1
for i in range(M):
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    s[a-1][b-1] = 1
    s[b-1][a-1] = 1
path = [1]
dfs(cnt, 1, path)

print(ans)

Solution (Python):
N,M=map(int,input().split())
G=[[False]*(N+1) for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a][b]=True
    G[b][a]=True

visited=[False]*(N+1)

visited[1]=True
def dfs(start):
    global N
    global visited
    all_visited=True
    sum=0

    for p in range(1,N+1):
        if not visited[p]:
            all_visited=False

    if all_visited:
        return 1
    else:
        for next in range(1,N+1):
            if not G[start][next]:
                continue
            if visited[next]:
                continue
            visited[next]=True
            sum+=dfs(next)
            visited[next]=False   

        return sum

print(dfs(1))

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

glaph={}

for i in range(1,n+1):
    glaph[i]=[]

for _ in range(m):
    a,b=map(int,input().split())
    glaph[a].append(b)
    glaph[b].append(a)



import itertools
junretsu=[]
for i in range(2,n+1):
    junretsu.append(i)
cnt=0

junretsu=list(itertools.permutations(junretsu))


for item in junretsu:
    i=0
    flag=0
    if item[0] not in glaph[1]:
        flag=1

    while i<n-2:
        
        if item[i+1] not in glaph[item[i]]:
            flag=1
        i+=1
    if flag==0:
        cnt+=1
        
print(cnt)

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

ab=[list(map(int,input().split())) for i in range(M)]

ans=0
stack=[]

for i in ab:
    if i[0]==1:
        stack.append([i[1],1+2**(i[1]-1)])

while len(stack)>0:
    p=stack.pop()

    if p[1]==2**N-1:
        ans+=1
    else:
        for i in ab:
            if i[0]==p[0] and not(2**(i[1]-1)&p[1]):
                stack.append([i[1],p[1]+2**(i[1]-1)])
            if i[1]==p[0] and not(2**(i[0]-1)&p[1]):
                stack.append([i[0],p[1]+2**(i[0]-1)])

print(ans)

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

ab=[list(map(int,input().split())) for i in range(M)]

ans=0
stack=[]

for i in ab:
    if i[0]==1:
        stack.append([i[1],1+2**(i[1]-1)])

while len(stack)>0:
    p=stack.pop()

    if p[1]==2**N-1:
        ans+=1
    else:
        for i in ab:
            if i[0]==p[0] and not(2**(i[1]-1)&p[1]):
                stack.append([i[1],p[1]+2**(i[1]-1)])
            if i[1]==p[0] and not(2**(i[0]-1)&p[1]):
                stack.append([i[0],p[1]+2**(i[0]-1)])

print(ans)

Solution (Python):
def main():
    import sys
    from itertools import permutations
    
    readlines = sys.stdin.readlines
    N, M = map(int, input().split())
    edge = [[0] * N for _ in range(N)]
    for s in readlines():
        a, b = map(int, s.split())
        a -= 1; b -= 1
        edge[a][b] = 1
        edge[b][a] = 1

    cnt = 0
    for path in permutations(range(1, N)):
        path = [0] + list(path)
        for i in range(N - 1):
            v = path[i]
            nv = path[i + 1]
            if edge[v][nv] == 0:
                break
        else:
            cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]

graph = defaultdict(list)
rinsetsu = [[0] * N for i in range(N)]

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    rinsetsu[a-1][b-1] = 1
    rinsetsu[b-1][a-1] = 1

per = list(permutations([n for n in range(1, N)]))
permu = []
for p in per:
    p = [0] + list(p)
    permu.append(p)
ans = 0
for p in permu:
    cnt = 0
    for i in range(N-1):
        a, b = p[i], p[i+1]
        if rinsetsu[a][b] == 1:
            cnt += 1
    if cnt == N - 1:
        ans += 1
print(ans)

Solution (Python):
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))

def dfs(g,e,now,ret):
    e[now] = True
    if all(e): ret += 1
    for next in g[now]:
        if e[next]: continue
        ret = dfs(g,e,next,ret)
    e[now] = False
    return ret

def main():
    n, m = MII()
    g = {i: [] for i in range(n)}
    for _ in range(m):
        x, y = MIIZ()
        g[x].append(y)
        g[y].append(x)
    ret = 0
    e = [False]*n
    e[0] = True
    ret = dfs(g,e,0,ret)
    print(ret)

if __name__ == '__main__':
    main()

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

def ok(l):
    return all([edge[l[i]-1][l[i+1]-1] for i in range(n-1)])
ans = 0
for x in itertools.permutations(range(2,n+1)):
    l = [1] + list(x)
    if ok(l):
        ans += 1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges=set()
for _ in range(M):
  a,b=map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))
  
  
answer=0


for p in itertools.permutations(range(1,N+1)):
  if p[0] !=1:
    continue
  bl=True
  for i in range(N-1):
    if (p[i],p[i+1]) not in edges:
      bl =False
      
  if bl:
    answer +=1
    
    
print(answer)

Solution (Python):
N,M=map(int,input().split())
a=[0 for k in range(M)]
b=[0 for k in range(M)]
for k in range(M):
    a[k],b[k]=map(int, input().split())
def dfs(route,new):
    route=route+new
    if len(route)==N+1:
        return 1
    count=0
    for k in range(M):
        if a[k]==route[-1] and b[k] not in route:
            count+= dfs(route,[b[k]])
    for k in range(M):
        if b[k]==route[-1] and a[k] not in route:
            count+= dfs(route,[a[k]])
    return count

print(dfs([0],[1]))

Solution (Python):
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edges, now, ret):
    edges[now] = True
    if all(edges): ret += 1

    for next in graph[now]:
        if edges[next]: continue
        ret = dfs(graph, edges, next, ret)
    edges[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edges = [False] * N
    edges[0] = True
    ret = dfs(g, edges, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
n,m = map(int,input().split())
ways = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    ways[a-1].append(b-1)
    ways[b-1].append(a-1)
checklist = [0]*n
position = 0 
cnt = 0
if n == 2:
    if 1 in ways[0]:
        print(1)
    else:
        print(0)
    exit()
for p in itertools.permutations(range(1,n)):
    if p[0] in ways[0]:
        flag = True
        for i in range(n-2):
            if p[i+1] not in ways[p[i]]:
                flag = False
                break
        if flag:
            cnt += 1
print(cnt)

Solution (Python):
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edgs, now, ret):
    edgs[now] = True
    if all(edgs): ret += 1

    for next in graph[now]:
        if edgs[next]: continue
        ret = dfs(graph, edgs, next, ret)
    edgs[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edgs = [False] * N
    edgs[0] = True
    ret = dfs(g, edgs, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import itertools
n, m = map(int, input().split())
e = [set(map(int, input().split())) for _ in range(m)]

n_list = []
for i in range(1, n+1):
    n_list.append(i)
n_array = sorted(list(itertools.permutations(n_list)))

count = 0

for i in range(math.factorial(n-1)):
    for j in range(n-1):
        if not (set(n_array[i][j:j + 2]) in e):
            break
    else:
        count += 1
print(count)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges=set()
for _ in range(M):
  a,b =map(int,input().split())
  edges.add((a,b))
  edges.add((b,a))
  
  
answer=0


for p in itertools.permutations(range(1,N+1)):
  if p[0] !=1:
    continue
  bl=True
  for i in range(N-1):
    if(p[i],p[i+1]) not in edges:
      bl =False
      break
  if bl:
    answer +=1
    
    
print(answer)

Solution (Python):
import itertools
N,M=map(int,input().split())
edges={tuple(sorted(map(int,input().split()))) for i in range(M)}
ans=0
for i in itertools.permutations(range(2,N+1),N-1):
    l=[1]+list(i)
    ans+=sum(1 for edge in zip(l,l[1:]) if tuple(sorted(edge)) in edges)==N-1
print(ans)

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

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

def solve(route):
    if len(route) == n:
        return 1
    count = 0
    for i in path[route[-1]]:
        if i in route: continue
        count += solve(route + [i])
    return count

print(solve([0]))

Solution (Python):

from collections import deque

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

count=0
stack=deque([str(0)])
while stack:
    tmp=stack.pop()
    if len(tmp)==N:
        count+=1
    else:
        label=[-1]*N
        for i in range(len(tmp)):
            label[int(tmp[i])]=1
        for i in friend[int(tmp[-1])]:
            if label[i]==-1:
                stack.append(tmp+str(i))
print(count)

Solution (Python):
import itertools as it

N, M = map(int, input().split())
ab = tuple(set(map(int, input().split())) for _ in range(M))

P = it.permutations(range(1, N + 1), N)

res = 0
for p in P:
    if p[0] == 1:
        for i in range(N - 1):
            if not(set({p[i], p[i + 1]}) in ab):
                break
        else:
            res += 1

print(res)

Solution (Python):
import itertools as it

N, M = map(int, input().split())
ab = tuple(set(map(int, input().split())) for _ in range(M))

P = it.permutations(range(1, N + 1), N)

res = 0
for p in P:
    if p[0] == 1:
        for i in range(N - 1):
            if not(set({p[i], p[i + 1]}) in ab):
                break
        else:
            res += 1

print(res)

Solution (Python):
import itertools

N,M = map(int,input().split())
lis = [x+1 for x in range(N-1)]
path = [list(map(int, input().split())) for _ in range(M)]
pb = [[False] * N for i in range(N)]
for i in range(M):
  p = path[i][0]-1
  q = path[i][1]-1
  pb[p][q] = True
  pb[q][p] = True

c = 0
for ps in itertools.permutations(lis):
  if pb[0][ps[0]]:
    for i in range(N-2):
      if not pb[ps[i]][ps[i+1]]:
        break
    else:
      c += 1

print(c)

Solution (Python):
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [[] for _ in range(n)]
for a, b in zip(*[iter(ab)] * 2):
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

def main():
    stack = [(0, 0)]
    paths = 0
    while stack:
        i, visited = stack.pop()
        visited |= 1 << i
        if visited == (1 << n) - 1:
            paths += 1
            continue
        for j in graph[i]:
            if visited >> j & 1: continue
            stack.append((j, visited))
    print(paths)

if __name__ ==  '__main__':
    main()

Solution (Python):
import itertools

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

path = [[False] * n for i 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(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):
from itertools import permutations as pmt

N,M = [int(x) for x in input().split()]

import numpy as np
Mat = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = [int(x) for x in input().split()]
    Mat[a-1][b-1] = 1

Mat = np.array(Mat)
Mat += Mat.T

ans = 0
for od in pmt([i for i in range(1,N)]):
    order = [0] + list(od)
    ok = True
    for i in range(N-1):
        ok &= (Mat[order[i]][order[i+1]] > 0)
    ans += int(ok)    

print(ans)

Solution (Python):
Vertex, Line = map(int, input().split())
LineList = [[int(_) for _ in input().split()] for i in range(Line)]
graph = [[] for _ in range(Vertex)]

for a, b in LineList:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

total_one_stroke_path = 0
def search_path(now_node = 0, check_passed = 0):
    check_passed += 1 << now_node
    global total_one_stroke_path

    for next_node in graph[now_node]:
        if check_passed & (1 << next_node) == 0:
            search_path(next_node, check_passed)

    if check_passed == (1 << Vertex) - 1:
        total_one_stroke_path += 1

    return

search_path()
print(total_one_stroke_path)
exit()

Solution (Python):
from collections import deque
from copy import deepcopy
n, m = map(int, input().split())
tree = [[] for i in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
result = 0
visit = [-1 for _ in range(n+1)]
visit[1] = 1
q = deque([[1, deepcopy(visit)]])
while q:
    p, v = q.pop()
    if v[p] == n:
        result += 1
    for j in tree[p]:
        if v[j]<0:
            next_v = deepcopy(v)
            next_v[j] = next_v[p]+1
            q.appendleft([j, next_v])
print(result)

Solution (Python):




import sys
input = sys.stdin.readline



def dfs(now,N,sides,visited):

    all_visited = True

    if False in visited:
        all_visited = False

    if all_visited:
        return 1

    res = 0

    for i in range(N):
        if not sides[now][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        res += dfs(i,N,sides,visited)
        visited[i] = False

    return res


def main():
    N,M = map(int,input().split())

    sides = [[False for j in range(N)] for i in range(N)]

    for i in range(M):
        A,B = map(int,input().split())
        sides[A-1][B-1] = sides[B-1][A-1] = True

    visited = [False for i in range(N)]
    visited[0] = True

    res = dfs(0,N,sides,visited)

    print(res)



main()

Solution (Python):
n,m = map(int,input().split())
input_lines = [[int(j)-1 for j in input().split()] for i in range(m)]

map_list = [[] for i in range(n)]

for line in input_lines:
    map_list[line[0]].append(line[1])
    map_list[line[1]].append(line[0])

stack = [[0],]
visited = [0 for i in range(n)]

def dfs(stack,visited):
    if sum(visited)==n:
        return 1
    ans = 0
    
    search = stack.pop(-1)
    for s in search:
        if visited[s]==1:
            continue
        visited[s]=1
        stack.append(map_list[s])
        ans += dfs(stack,visited)
        visited[s]=0
    return ans

ans = dfs(stack,visited)
print(ans)

Solution (Python):
import itertools

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

graph = [[False for i in range(n)] for j in range(n)]

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

ans = 0
for i in itertools.permutations(range(n)):
    if i[0] != 0:
        continue
    visited = [0]*n
    visited[0] += 1
    for j in range(n):
        if j == n-1:
            if 0 not in visited:
                ans += 1
            break
        if graph[i[j]][i[j+1]] == True:
            visited[i[j+1]] += 1
        
            
print(ans)

Solution (Python):
def dfs(i,d,c):
    global n,f,ans
    c2=c.copy()
    c2[d]=1
    
    if i==n:
        ans+=1
        return
    for j in range(n):
        
        if (f[d][j]==1 or f[j][d]==1) and c2[j]==0:
            
            dfs(i+1,j,c2)

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

dfs(1,0,c1)
print(ans)

Solution (Python):
import itertools

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

lst = [[0 for _ in range(n)] for _ in range(n)]

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

l = list(range(n))

cnt = 0
for v in itertools.permutations(l):
	flg = True
	if v[0] == 0:
		for i in range(n-1):
			x, y = v[i], v[i + 1]
			if lst[x][y] == 0: 
				flg = False
		if flg:
			cnt += 1

print(cnt)

Solution (Python):










"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:
    return a
  return gcd_(a,a % b) 
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7

n,m = readInts()
a = [0] * m
b = [0] * m

graph = [[False for i in range(n)] for j in range(n)]

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

cnt = 0
now = [0] * n

def dfs(pos,nya):
  global cnt
  if pos == n:
    if now[0] == 0:
      for i in range(n-1):
        if graph[now[i]][now[i+1]] == False:
          break
        if i == n-2:
          cnt += 1
    return
  for i in range(n):
    if nya & (1 << i):
      now[pos] = i
      dfs(pos+1,nya^(1<<i))
dfs(0,(1<<n)-1)
print(cnt)

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

from itertools import permutations
ans=0
for p in permutations([x for x in range(1,n)]):
    ok=True
    t=[0]+list(p)
    for i in range(1,n):
        if G[t[i-1]][t[i]]==0:ok=False
    if ok:ans+=1
print(ans)

Solution (Python):
import itertools
N, M = map(int,input().split())
AB = [0] * M
for i in range(M):
  AB[i] = list(map(int, input().split()))
  
lis = [x for x in range(1, N + 1)] 
 
permutations_lis = itertools.permutations(lis)


ans = 0
for one_case in permutations_lis: 
  
  if one_case[0] == 1:
    m = 0
  else:
    m = N
  for i in range(N - 1):
    
    path = [one_case[i], one_case[i + 1]]
    path2 = [one_case[i + 1], one_case[i]]
    if path in AB:
      m += 1
    elif path2 in AB:
      m += 1
  if m == N - 1:
    ans += 1
    
print(ans)

Solution (Python):
import copy
class Node:
    def __init__(self):
        self.adjacentnode=[]

def search(lista,nodet):
    global count
    global n
    if len(lista)==n:
            count+=1
            return True
    for a in nodet[lista[-1]].adjacentnode:
        if a not in lista:
                newlist=copy.copy(lista)
                newlist.append(a)
                search(newlist,nodet)

n,m=map(int,input().split()) 
count=0
listsrch=[0]
nodelist=[Node() for a in range(n)]
for t in range(m):
    a,b=map(int,input().split())
    nodelist[a-1].adjacentnode.append(b-1)
    nodelist[b-1].adjacentnode.append(a-1)
search(listsrch,nodelist)
print(count)

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

    visited = [False]*N
    visited[0] = True
    ans = 0

    def dfs(v: int):
        nonlocal visited
        nonlocal ans
        if all(visited):
            ans += 1
            return
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            dfs(n)
            visited[n] = False
        return

    dfs(0)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
INF = 10**18
matrix = [[INF]*N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    matrix[a][b] = 1
    matrix[b][a] = 1

ans = 0


for p in permutations(range(1, N)):
    ok = True
    cur = 0
    for pi in p:
        if matrix[cur][pi] == INF:
            ok = False
            break
        cur = pi
    if ok:
        ans += 1

print(ans)

Solution (Python):
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    N, M = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    def dfs(v=0, visited=1 << 0):
        if visited == (1 << N) - 1:
            return 1

        ret = 0
        for u in g[v]:
            if (visited >> u) & 1:
                continue
            ret += dfs(u, visited | (1 << u))
        return ret

    ans = dfs()
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import copy
import sys
sys.setrecursionlimit(50000000) 


N, M = map(int, input().split())
l = []

for i in range(M):
    l.append(list(map(lambda x: int(x)-1 , input().split())))

lis = [[] for i in range(N)]

for i in range(M):
    lis[l[i][0]].append(l[i][1])
    lis[l[i][1]].append(l[i][0])

def dfs():
    re=0
    q1 =[[0]*N]
    q2=[0]
    while len(q1) != 0:
         
        visited=q1.pop()
        v=q2.pop()
        visited[v]=1
        if all(visited[c]==1 for c in range(N)):
            re += 1
        elif len(lis[v]) != 0:
            for i in lis[v]:
                if visited[i] == 0:
                    hoge=copy.deepcopy(visited)                    
                    q1.append(hoge)
                    q2.append(i)
    return re

print(dfs())

Solution (Python):
import sys
sys.setrecursionlimit(10**7)


def dfs(v):
    global ans
    if all(visited[i] == 1 for i in range(n)):
        ans = ans + 1
        return
    for i in range(n):
        if gra[v][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0
    return


if __name__ == '__main__':
    n, m = map(int, input().split())
    ans = 0
    visited = [0]*n
    gra = [[0]*n for _ in range(n)]
    visited[0] = 1
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        gra[a][b] = 1
        gra[b][a] = 1
    dfs(0)
    print(ans)

Solution (Python):
import itertools

n,m = [int(i) for i in input().split()]

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

ans = 0

for i in itertools.permutations(range(n),n):
  if i[0] == 0:
    for j in range(n):
      if j == n-1:
        ans += 1
        break
      if chk[i[j]][i[j+1]] != 1:
        break
print(ans)

Solution (Python):

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


ab += [[b,a] for a,b in ab]


abi = [[] for _ in range(n+1)]
for i,(a,b) in enumerate(ab):
    abi[a].append(b)




import sys
sys.setrecursionlimit(4100000)

def dfs(idx=1,visitted=[1],cnt=1):
    ret = 0
    if cnt==n:
        return 1
    for to in abi[idx]:
        if to not in visitted:
            ret += dfs(to,visitted+[to],cnt+1)
    return ret
print(dfs())

Solution (Python):
from itertools import permutations

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

ans = 0
for comb in permutations(range(1, N), N-1):
    v = 0
    valid = True
    for i in comb:
        if i not in graph[v]:
            valid = False
            break
        v = i
    if valid:
        ans += 1

print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(M)]
G = [set() for i in range(N)]

for a, b in ab:
    a -= 1
    b -= 1
    G[a].add(b)
    G[b].add(a)

ans = 0
for x in permutations(range(1, N)):
    if x[0] in G[0]:
        for i in range(N-1):
            if i < N-2:
                if x[i+1] in G[x[i]]:
                    continue
                else:
                    break
            else:
                ans += 1
print(ans)