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):
from itertools import permutations
N,M = map(int,input().split())
E = [[False for _ in range(N)] for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    E[a-1][b-1] = True
    E[b-1][a-1] = True

P = permutations([i for i in range(1,N)])

ans = 0
for pp in P:
    l = len(pp)
    ni,mi = 0,0
    chk = True
    for p in pp:
        mi = p
        if not E[ni][mi]:
            chk = False
            break
        ni = p
    if chk:
        ans += 1

print(ans)

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

nodes = {}
for n in range(N):
    nodes[n] = []

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


def dfs(v):
    global reached
    global ans
    if False not in reached:
        ans += 1
        return
    for i in range(N):
        if i in nodes[v] and not reached[i]:
            reached[i] = True
            dfs(i)
            reached[i] = False
    return

ans = 0
for v in range(1):
    reached = [False for i in range(N)]
    reached[v] = True
    dfs(v)
print(ans)

Solution (Python):
from itertools import permutations

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

Matrix = [[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
    Matrix[a][b] = True
    Matrix[b][a] = True

for i in range(N) :
    Matrix[i][i] = True

arange = list(range(2,N+1))

ans = 0
for pm in permutations(arange) :
    pm = [1] + list(pm)
    for row,col in zip(pm,pm[1:]) :
        row -= 1
        col -= 1
        if not Matrix[row][col] :
            break
    else :
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

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

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

for i in range(N) :
    Matrix[i][i] = True
for i in range(M) :
    row,col = map(int,input().split())
    row -= 1
    col -= 1
    Matrix[row][col] = True
    Matrix[col][row] = True

arange = range(2,N+1)

ans = 0
for pm in permutations(arange) :
    pm = [1] + list(pm)
    for row,col in zip(pm,pm[1:]) :
        row -= 1
        col -= 1
        if not Matrix[row][col] :
            break
    else :
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations

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

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

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

arange = range(2,N+1)

res = 0
for P in permutations(arange) :
    P = [1] + list(P)
    for S,G in zip(P,P[1:]) :
        if not L[S-1][G-1] :
            break
    else :
        res += 1
print(res)

Solution (Python):
n,m=[int(i) for i in input().split()]
pp=[[0 for i in range(2)] for j in range(m)]
not_bridge=0




def dfs(Graph, Start, Vn, Visited=None):
  

  if Graph[Start]==[] and Visited==None: 
        Next=Start+1
        dfs(Graph, Next, Vn, Visited)  
  else:


    if (Visited==None): 
        Visited = [] 
        Visited.append(Start)  

    
    if len(Visited)==Vn: 
        
        global not_bridge
        if len(set(Visited)) == n:
            not_bridge=not_bridge+1

        return 0
        
    for Next in Graph[Start]:  
        Visited.append(Next)
        
        dfs(Graph, Next, Vn, Visited)  
        Visited.pop()
    return 0
  


for i in range(m) :
    pp[i] =[int(i) for i in input().split()]
    

l = [[] for i in range(n+1)] 
for pi in pp:  
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])


dfs(l, 0, n)
print(not_bridge)

Solution (Python):
n,m=map(int,input().split())
l=[]
for i in  range(m):
    a=[int(i) for i in input().split()]
    l.append(a)

ans=[]
li=[0 for i in range(n+1)]

def dfs(a,r):
    r[a]=1
    p=0
    q=0
    for i in range(m):
        if l[i][0]==a or l[i][1]==a:
            q+=1
            b=l[i][0]*l[i][1]//a
            if r[b]==0:
                dfs(b,r)
                r[b]=0
            else:
                p+=1
    if p==q and sum(r)==n:
        ans.append(1)

dfs(1,li)
print(sum(ans))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import permutations

n,m = li()
graph = [[False]*n for _ in range(n)]

for _ in range(m):
    a,b = li_()
    graph[a][b] = True
    graph[b][a] = True
    
cands = list(permutations([i for i in range(1,n)]))

ans = 0

for c in cands:
    cand = [0] + list(c)
    ok = True
    for i in range(n-1):
        if not graph[cand[i+1]][cand[i]]:
            ok = False
    
    if ok:   
        ans += 1
    
print(ans)

Solution (Python):
import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)

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

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


l = range(2,n+1)

res = 0
for p in perm(l):
    p = [1] + list(p)
    for s,g in zip(p,p[1:]):
        if not coor[s-1][g-1]:
            break
    else:
        res += 1
print(res)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [[] for _ in range(N)]
cou = 0

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

def search(path):
    global cou
    n = path[len(path) - 1]
    if len(path) == N:
        cou += 1
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                search(path)
                path.pop()

search([0])
print(cou)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [[] for _ in range(N)]
cou = 0

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

def search(path):
    global cou
    n = path[len(path) - 1]
    if len(path) == N:
        cou += 1
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                search(path)
                path.pop()

search([0])
print(cou)

Solution (Python):
import itertools
def course_judge(edge,arr):
    ok = True
    for i in range(1,len(arr)):
        go = arr[i-1]
        to = arr[i]
        if edge[go][to] == 0 or edge[to][go] == 0:
            ok = False
    return ok

N,M = map(int,input().split())
arr = [i for i in range(1,N+1)]
edge = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    go,to = map(int,input().split())
    edge[go][to] = 1
    edge[to][go] = 1
count = 0
for a in itertools.permutations(arr):
    if a[0] == 1 and course_judge(edge,a):
        count += 1
print(count)

Solution (Python):
import itertools

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

ans = 0
for ex in itertools.permutations(example):
    e = [0] + list(ex)
    for a, b in zip(e, e[1:]):
        if path[a][b] is False:
            break
    else:
        
        ans += 1
print(ans)

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

for i in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
queue = [(1,)]
ans = 0
while queue:
    q = queue.pop()

    if len(q) == N:
        ans+=1
        continue
    now = q[-1]

    for nextp in adj[now]:
        if not nextp in q:
            queue.append(q+(nextp,))
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
edge=[]
for i in range(N+1):
  edge.append([0]*(N+1))
for j in range(M):
  a,b=map(int,input().split())
  edge[a][b]=1
  edge[b][a]=1
roots=list(itertools.permutations(range(2,N+1)))
ans=0
for root in roots:
  pos=1
  for i in range(N-1):
    nxt=root[i]
    if edge[pos][nxt]==1:
      pos=nxt
    else:
      break
  else:
    ans+=1
print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
L=[]
c=[i for i in range(1,N+1)]
for _ in range(M):
    x,y = map(int,input().split())
    l1 = [x,y]
    l2 = [y,x]
    L.append(l1)
    L.append(l2)
c = [list(x) for x in itertools.permutations(c)]
count = 0
ans = 0
for x in c:
    if x[0] > 1:
        break

    for i in range(N-1):
        if [x[i],x[i+1]] in L:
            count += 1
 
            if count == N - 1:
                ans += 1
                count = 0
        else:
            count = 0
            break

print(ans)

Solution (Python):
from itertools import permutations

N,M=map(int,input().split())
L=[]
for i in range(N-1):
    L.append(1+i)
A=[]
a=[]
for i in range(N):
    for j in range(N):
        a.append(10)
    A.append(a)
    a=[]
    


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


cnt=0
for i in permutations(L,len(L)):
    S=0
    for j in range(len(i)-1):
        if A[i[j]][i[j+1]]==10:
            break
        else:
            S+=1
    if S==len(L)-1:
        if A[0][i[0]]==1:
            cnt+=1
print(cnt)

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

def dfs(v, n, visited):
    all_visited = True

    for i in range(N):
        if visited[i] == False:
            all_visited = False

    if all_visited == True:
        return 1

    ret = 0

    for i in range(N):
        if edge[v][i] == 0: 
            continue
        if visited[i]: 
            continue

        visited[i] = True
        ret += dfs(i, N, visited)
        visited[i] = False

    return ret


visited = [False] * N

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

Solution (Python):
n, m = list(map(int, input().split()))
d = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if a not in d:
        d[a] = [b]
    else:
        d[a].append(b)
    if b not in d:
        d[b] = [a]
    else:
        d[b].append(a)

ans = 0

def DFS(now, visited):
    global ans
    if len(visited) == n:
        ans += 1
        return
    for i in d[now]:
        if i not in visited:
            DFS(i, visited + [i])

DFS(0, [0])
print(ans)

Solution (Python):
import copy
s=list()

N,M=map(int,raw_input().split())
n=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
        a,b=map(int,raw_input().split())
        n[a-1][b-1]=1
        n[b-1][a-1]=1
arrived=[0 for i in range(N)]

arrived[0]=1
def solve(s,arrived):
        narrived=copy.deepcopy(arrived)
        global n
        global N
        op=False
        ans=0
        for i in range(N):
                arrived=copy.deepcopy(narrived)
                if(s[i]==1 and arrived[i]!=1):
                        op=True
                        arrived[i]=1
                        ans+=solve(n[i],arrived)
        
        if(sum(arrived)==N and op==False):
                return 1
        elif(op==False):
                return 0
        return ans
                        
print(solve(n[0],arrived))

Solution (Python):
import itertools
n, m = map(int, input().split())
c = []
for i in range(m):
    c.append([int(m) for m in input().split()])
c.sort()
d = []
for i in range(n):
    d.append([])
for i in range(m):
    for k in range(n):
        if c[i][0] == k + 1:
            d[k].append(c[i][1])
        if c[i][1] == k + 1:
            d[k].append(c[i][0])
nli = [i + 1 for i in range(1, n)]
ans = 0
for path in itertools.permutations(nli, n - 1):
    for i in range(len(path) - 1):
        if i == 0:
            if path[i] in d[0]:
                if path[i + 1] in d[path[i] - 1]:
                    pass
                    if i == len(path) - 2:
                        ans += 1
                else:
                    break
            else:
                break
        else:
            if path[i + 1] in d[path[i] - 1]:
                pass
                if i == len(path) - 2:
                    ans += 1
            else:
                break
if n == 2:
    ans += 1
print(ans)

Solution (Python):
def dfs(v, n, visited, graph):
    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, n, visited, graph)
        visited[i] = False
    return ret


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

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

visited = [False for _ in range(n)]
visited[0] = True
print(dfs(0, n, visited, graph))

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a] += [b]
    edges[b] += [a]
candy = [[1]]
for _ in range(N - 1):
    tmp = []
    for c in candy:
        for next in edges[c[-1]]:
            tmp += [c + [next]]
    candy = tmp
print(sum(len(set(c)) == N for c in candy))

Solution (Python):
from itertools import permutations

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))

cnt = 0
for p in permutations(range(2, N + 1)):
    cnt += all(move in edges for move in zip((1,) + p, p))
print(cnt)

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

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

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



ans = 0
visited = [0 for _ in range(n)]

def dfs(v):
    visited[v] = 1
    if all(x == 1 for x in visited):
        global ans
        ans += 1
        return

    for i in range(n):
        if g[v][i] == 1 and visited[i] == 0:
            visited[i] = 1
            dfs(i)
            visited[i] = 0

    return

dfs(0)
print(ans)

Solution (Python):
n, m = map(int, input().split())
edge = [[False for j in range(n)] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	edge[a-1][b-1] = edge[b-1][a-1] = True
visited = [False for _ in range(n)]
ans = 0
def dfs(v):
	visited[v] = True
	if all(x==True for x in visited):
		global ans
		ans += 1
		return
	for i in range(0, n):
		if edge[v][i]==True and visited[i]==False:
			dfs(i)
			visited[i] = False
dfs(0)
print(ans)

Solution (Python):
from itertools import permutations

N, M = map(int, input().split())
matrix = [[0] * N for i in range(N)]
ans = 0

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

for order in list(permutations(range(N))):
    if order[0] != 0:
        break
        
    check = 1
    for i in range(N-1):
        check *= matrix[order[i]][order[i+1]]
    ans += check
    
print(ans)

Solution (Python):
from itertools import permutations as perm
n,m = map(int,input().split())
coor = [[False]*n for _ in range(n)]
for i in range(m):
	a,b = map(int,input().split())
	a,b = a-1,b-1
	coor[a][b] = True
	coor[b][a] = True
ll = list(range(n))
res = 0
for l in perm(ll):
	if l[0]!=0:
		continue
	for (i,j) in zip(l,l[1:]):
		if not coor[i][j]:
			break
	else:
		res += 1
print(res)

Solution (Python):
import itertools
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

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

Solution (Python):
import itertools

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

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

X = [i for i in range(1, N)]

ans = 0
for s in itertools.permutations(X, N - 1):
	judge = "Yes"
	x = 0
	for i in s:
		if L[i].count(x) == 1:
			pass
			x = i
		else:
			judge = "No"
			break
	if judge == "Yes":
		ans += 1

print(ans)

Solution (Python):
n = 0
g = []
res = 0


def dfs(i, path):
    global n, g, res
    path.append(i)
    if len(path) == n:
        res += 1
        path.pop()
        return

    for j in g[i]:
        if not j in path:
            dfs(j, path)
    path.pop()


def main():
    global n, g, res
    n, m = map(int, input().split())
    g = [set() for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        g[a].add(b)
        g[b].add(a)

    path = []
    dfs(0, path)
    print(res)


if __name__ == '__main__':
    main()

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

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

for i in range(m):
  s,t = map(int,input().split())
  edges[s-1].append(t-1)
  edges[t-1].append(s-1)

cnt =0

V=[0]*n

def dfs(V,s):
  global cnt
  V=V[:]
  V[s]=1
  if sum(V)==n:
    cnt+=1
  else:
    for v in edges[s]:
      if V[v]==0:
        dfs(V,v)
  
dfs(V,0)
print(cnt)

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

check = [False for i in range(n)]

ans = 0
def dfs(v):
    global ans

    if check.count(True) == n:
        ans += 1
        return
    else:
        for next in matrix[v]:
            if not check[next]:
                check[next] = True
                dfs(next)
                check[next] = False
        return

check[0] = True
dfs(0)

print(ans)

Solution (Python):
def c_one_stroke_path(N, M, E):
    from itertools import permutations
    edge = [[] for j in range(N + 1)]
    for a, b in E:
        edge[a].append(b)
        edge[b].append(a)

    ans = 0
    
    routes = permutations(range(2, N + 1), N - 1)
    for route in routes:
        r = [1] + list(route)
        for i in range(len(r) - 1):
            if not r[i + 1] in edge[r[i]]:
                break  
        else:
            ans += 1  
    return ans

N,M = [int(i) for i in input().split()]
E = [[int(i) for i in input().split()] for j in range(M)]
print(c_one_stroke_path(N, M, E))

Solution (Python):
N, M = [int(_) for _ in input().split()]
ab = [[int(_) - 1 for _ in input().split()] for _ in range(M)]

G = [[0] * N for _ in range(N)]

for a, b in ab:
    G[a][b] = 1
    G[b][a] = 1

count = 0


def dfs(G, a, x):
    a[x] = 1
    if all(a):
        return 1
    else:
        count = 0
        for j in range(N):
            if G[x][j] == 1 and a[j] == 0:
                count += dfs(G, a.copy(), j)
        return count


print(dfs(G, [0] * N, 0))

Solution (Python):
v=[]
n,m=map(int,input().split())
ans=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    ans[a-1].append((b-1))
    ans[b-1].append((a-1))
def dfs(now,visited=[]):
    if len(visited)==n:
        v.append([visited])
        return
    for j in ans[now]:
        if j not in visited:
            dfs(j,visited+[j])
dfs(0,[0])
print(len(v))

Solution (Python):


from itertools import permutations

def main():
    ans = 0
    n, m = map(int, input().split())
    G = [[] for _ in range(n) ]

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        G[a] += [b]
        G[b] += [a]

    a = list(permutations(range(1, n)))

    for i in a:
        ok = True
        for j in range(len(i)):
            tmp = False
            if j == 0:
                for e in G[0]:
                    if e == i[j]:
                        tmp = True
            else:
                for e in G[i[j-1]]:
                    if e == i[j]:
                        tmp = True
            if not tmp:
                ok = False
        if ok:
            ans += 1

    print(ans)

main()

Solution (Python):


import sys

sys.setrecursionlimit(10000)
ans = 0

def dfs(cur, visited, G):
    visited[cur] = True

    if all(visited):
        global ans
        ans += 1

    for c in G[cur]:
        if not visited[c]:
            dfs(c, visited, G)
            visited[c] = False
    return


def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n) ]

    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        G[a] += [b]
        G[b] += [a]

    v = [ False for _ in range(n) ]

    dfs(0, v, G)
    print(ans)

main()

Solution (Python):
from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [[False] * N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a][b] = True
        adj[b][a] = True
    retval = 0
    q = deque([(0, set([0]))])
    while len(q):
        cur, visited = q.popleft()
        if len(visited) == N:
            retval += 1
            continue
        for nxt in range(N):
            if nxt in visited:
                continue
            if adj[cur][nxt]:
                next_visited = set(visited)
                next_visited.add(nxt)
                q.append((nxt, next_visited))
    print(retval)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools

N, M = (int(i) for i in input().split())
sides = []
for i in range(M):
    a, b = (int(i) for i in input().split())
    sides.append((a-1,b-1))
kouhos = list(itertools.permutations(range(N)))
count = 0

for kouho in kouhos:
    Judge = True
    if kouho[0] != 0:
        break
    else:
        for i in range(N-1):
            if (kouho[i] , kouho[i+1]) in sides:
                pass
            elif (kouho[i+1] , kouho[i]) in sides:
                pass
            else:
                Judge = False
                break
    
    if Judge:
        count += 1

print(count)

Solution (Python):
from itertools import permutations

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

points = [i for i in range(1, N+1)]
answer = 0

for point in permutations(points):
  if not point[0] == 1:
    continue
  for i in range(N-1):
    if sorted([point[i], point[i+1]]) not in paths:
      break
  else:
    answer += 1

print(answer)

Solution (Python):

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

visited = [False for _ in range(n)]
def dfs(v):
    if all(visited):
        return 1
    res = 0
    for e in edge[v]:
        if not visited[e]:
            visited[e] = True
            res += dfs(e)
            visited[e] = False
    return res

visited[0] = True
print(dfs(0))

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

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

for i in range(M):
    a, b = map(int, input().split())
    V[a-1].append(b-1)
    V[b-1].append(a-1)
    
Log = [0]*N

def DFS(now_V, now_Log, ans):
    
    
    if sum(now_Log)==N:
        ans = ans+1
        
        return ans
    
    for i in V[now_V]:
        if now_Log[i]<1:
            now_Log[i]=1
            ans = DFS(i, now_Log, ans)
            now_Log[i]=0
    
    return ans
          

count = 0  

Log[0] = 1

print(DFS(0, Log, count))

Solution (Python):
num_route = 0
num_node = 0

def func(unvisited_paths, visited_node, current_node):
    global num_route
    if len(visited_node) == num_node:
            num_route += 1
            return
    for next_path in [path for path in unvisited_paths if (path[0] == current_node) and (path[1] not in visited_node)]:
        next_visited_node = visited_node + [next_path[1]]
        next_unvisited_paths = unvisited_paths[:]
        next_unvisited_paths.pop(next_unvisited_paths.index([current_node, next_path[1]]))
        next_unvisited_paths.pop(next_unvisited_paths.index([next_path[1], current_node]))
        next_current_node = next_path[1]
        
        func(next_unvisited_paths, next_visited_node, next_current_node)
    
    return

def main():
    global num_node
    num_node, num_path = map(int, input().split())
    unvisited_paths = [list(map(int, input().split())) for i in range(num_path)]
    for path in unvisited_paths[:]:
        unvisited_paths.append([path[1], path[0]])
    current_node, visited_node = 1, [1]
    func(unvisited_paths, visited_node, current_node)
    print(num_route)

if __name__ == '__main__':
    main()

Solution (Python):
def func(paths, passed_node, current_node, num_node):
    global num_route
    if len(passed_node) == num_node:
            num_route += 1
            return
    for next_path in [path for path in paths if (path[0] == current_node) and (path[1] not in passed_node)]:
        new_passed_node = passed_node + [next_path[1]]
        new_paths = paths[:]
        new_paths.pop(new_paths.index([current_node, next_path[1]]))
        new_paths.pop(new_paths.index([next_path[1], current_node]))
        new_current_node = next_path[1]
        
        func(new_paths, new_passed_node, new_current_node, num_node)
    
    return num_route
    
            


num_node, num_path = map(int, input().split())
paths = [list(map(int, input().split())) for i in range(num_path)]
for path in paths[:]:
    paths.append([path[1], path[0]])
current_node = 1
passed_node = [1]
num_route = 0

try:
    func(paths, passed_node, current_node, num_node)
finally:
    print(num_route)

Solution (Python):
import itertools

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


points = [i for i in range(1, N+1)]
ans = 0

for i, v in enumerate(list(itertools.permutations(points))):
    if not v[0] == 1:
        continue
    for j in range(N-1):
        if sorted([v[j], v[j+1]]) not in Paths:
            break
    else:  
        ans += 1


print(ans)

Solution (Python):
import copy


def search(start, adj, stack):
    nextNum = 0
    start[1][start[0]] = 1
    for i in range(len(adj[start[0]])):
        
        if adj[start[0]][i] == 1 and start[1][i] == -1:
            stack.append([i, copy.deepcopy(start[1])])
            
            nextNum += 1
            
            
    if nextNum > 0:
        return nextNum
    elif sum(start[1]) == len(adj):
        return 0
    else:
        return -1


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

visited = [-1 for i in range(n)]
visited[0] = 1
stack = [[0, visited]]
poped = []
count = 0
while 1:
    size = len(stack)
    
    if size == 0:
        
        break
    next = stack.pop()
    
    
    
    
    nextNum = search(next, adj, stack)
    if nextNum == 0:
        count += 1
        
    
        
print(count)

Solution (Python):
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

def search(S, history, counter):
    new_history = [i for i in history]
    new_history.append(S)
    if len(new_history) == N:
        counter += 1
        return counter
        
    for i in range(len(A)):
        if A[i] == S and not B[i] in history:
            counter = search(B[i], new_history, counter)

    for i in range(len(B)):
        if B[i] == S and not A[i] in history:
            counter = search(A[i], new_history, counter)

    return counter

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

Solution (Python):
n, m = map(int, input().split(" "))
ab = [list(map(int, input().split(" "))) for _ in range(m)]

s = [set() for _ in range(n)]
for ab_i in ab:
	a_i, b_i = map(lambda x: x-1, ab_i)
	s[a_i].add(b_i)
	s[b_i].add(a_i)



def dfs(num, visited=set()):
	visited = visited | {num}
	can_moves = s[num] - visited
	
	if not can_moves:
		return (len(visited) == n)
	return sum(dfs(can_move, visited) for can_move in can_moves)

print(dfs(0))

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=list(itertools.permutations(range(2,n+1)))
c=0
for j in range(len(L)):
  if [1,L[j][0]] in l:
    x=0
    for k in range(n-2):
      if [L[j][k],L[j][k+1]] in l or [L[j][k+1],L[j][k]] in l:x+=1
    if x==n-2:c+=1
print(c)

Solution (Python):




"""
https://beta.atcoder.jp/contests/abc054/tasks/abc54_c
"""

import sys
import math
import copy
from inspect import currentframe

def debug_print(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

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)
    


def dfs(node, visited_list):
    paths = 0
    visited = copy.copy(visited_list)
    if node not in visited:
        visited.append(node)
    debug_print(node)
    debug_print(visited_list)
    if len(visited) == N:
        return 1
    for to in graph[node]:
        if to not in visited:
            paths += dfs(to, visited)
    return paths
        
print(dfs(0, [0]))