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 copy


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def generate_patterns(remains, current_pattern, patterns):
    if len(remains) == 0:
        patterns.append(current_pattern)
        return
    for remain in remains:
        _current_pattern = copy.copy(current_pattern)
        _current_pattern.append(remain)
        _remains = copy.copy(remains)
        _remains.remove(remain)
        generate_patterns(_remains, _current_pattern, patterns)
    return patterns


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

m = {}
for i in range(1, N+1):
    m[i] = {}
    for j in range(1, N+1):
        m[i][j] = False

for line in lines:
    m[line.a][line.b] = True
    m[line.b][line.a] = True

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

cnt = 0
for pattern in patterns:
    countable = True
    for i in range(len(pattern)-1):
        current = pattern[i]
        next = pattern[i+1]
        if not(m[current][next]):
            countable = False
            break
    if countable:
        cnt += 1

print(cnt)

Solution (Python):
from collections import deque

N, M = map(int, raw_input().split())
nodes = {i:[] for i in range(1, N+1)}
for _ in range(M):
  a, b = map(int, raw_input().split())
  nodes[a] += [b]
  nodes[b] += [a]
stack = deque([[1, []]])
ans = 0
while stack:
  n, history = stack.pop()
  if len(history) == N - 1:
    ans += 1
    continue
  node = nodes[n]
  for next_node in node:
    if not next_node in history:
      stack.append([next_node, history+[n]])
print ans

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

l = [set() for _ in range(n)]
for a_i, b_i in ab:
	l[a_i-1].add(b_i-1)
	l[b_i-1].add(a_i-1)



def dfs(num, visited=set()):
	visited = visited | {num}
	can_moves = l[num] - visited
	
	if not can_moves:
		
		return (len(visited) == n)

	sum_num = 0
	for can_move in can_moves:
		sum_num += dfs(can_move, visited)
	return sum_num

print(dfs(0))

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

seq = tuple([x for x in range(2,n+1)])
route = list(itertools.permutations(seq))

ans = 0
for t in route:
    now = 1
    flag = True
    t = list(t)
    for i in t:
        (p,q) = (now,i) if now < i else (i,now)
        if [p,q] not in e:
            flag = False
            break
        now = i
    if flag:
        ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
Edge=[[int(i) for i in input().split()] for i in range(M)]
Vertex=[]
X=[]
n=1
a=0
while n<=N:
  while a<=M-1:
    if n in Edge[a]:
      X=X+Edge[a]
    a+=1
  X=[item for item in X if item!=n]
  Vertex.append(X)
  n+=1
  a=0
  X=[]
Choices=[[1]]
m=0
for i in Choices:
    if len(i)>=N:
      break
    for j in Vertex[i[len(i)-1]-1]:
      Choices.append(i+[j])
Choices=[item for item in Choices if len(item)==N]
a=1
while a<=N:
  Choices=[item for item in Choices if item.count(a)==1]
  a+=1
print(len(Choices))

Solution (Python):
n, m = map(int, input().split())
e = [set([]) for _ in range(n+1)] 
for _ in range(m):
    a, b = map(int, input().split())
    e[a].add(b)
    e[b].add(a)

ans = 0
visited = [False]*(n+1) 
visited[0] = True
def dfs(v):
    
    global visited
    global ans
    if all(v==True for v in visited):
        ans += 1
        return
    
    for next_pos in e[v]:
        if visited[next_pos] != True:
            visited[next_pos] = True
            dfs(next_pos)
            visited[next_pos] = False

visited[1] = True
dfs(1)
print(ans)

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(1000000)



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



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v



def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk



def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False



dp = None

ans = 0
N, M = 0, 0
A = None

def dfs(current_node, past_nodes, depth):
    global ans

    if depth == N:
        ans += 1
        return
    
    for next_node_i in range(1, N+1):
        if A[current_node][next_node_i] and next_node_i not in past_nodes:
            past_nodes.append(next_node_i)
            dfs(next_node_i, past_nodes, depth+1)
            past_nodes.remove(next_node_i)
    

def main():
    global N
    global M
    global A

    N, M = li_input()
    A = [[0] * (N+1) for _ in range(N+1)]

    for i in range(M):
        a, b = li_input()
        A[a][b] = 1
        A[b][a] = 1

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


main()

Solution (Python):
import itertools
N,M=map(int,input().split())
grid = []
for i in range(N):
    array = []
    while len(array) < N:
      array.append(0)
    grid.append(array)
for i in range(M):
    s,t=map(int,input().split())
    grid[s-1][t-1] = 1
    grid[t-1][s-1] = 1
i = 1
lis = []
while i <= N:
  lis.append(i)
  i += 1
ans = 0
for nums in itertools.permutations(lis):
    if nums[0]!=1:
      pass
    else:
      k = 0
      flag = 0
      while k < N-1:
        if grid[nums[k]-1][nums[k+1]-1] == 1:
          pass
        else:
          flag = 1
        k += 1
      if flag == 0:
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
G = {}
for i in range(0,M):
    a, b = list(map(int, input().split()))
    if a in G:
        G[a] += [b]
    else:
        G[a] = [b]
    if b in G:
        G[b] += [a]
    else:
        G[b] = [a]

from itertools import permutations
import copy
paths = list(map(lambda x: [1] + list(x),list(permutations(range(2,1+N),N-1))))
cnt = 0

for path in paths:
    _G = copy.deepcopy(G)
    flg = 1
    for i in range(1,N):
        if path[i] in _G[path[i-1]]:
            _G[path[i-1]].remove(path[i])
            _G[path[i]].remove(path[i-1])
        else:
            flg = 0
            break
    cnt += flg

print(cnt)

Solution (Python):

def dfs_mat(v):
    global adjacency_mat, ans, visited
    
    if sum(visited) == N:
        ans += 1
        return
    for i in range(N):
        if adjacency_mat[v][i]:
            
            if visited[i] == True:
                continue
            
            else:
            
                visited[i] = True
                dfs_mat(i)    
            
                visited[i] = False


if __name__ == "__main__":
    
    N, M = map(int, input().split())
    
    adjacency_mat = [[None]* N for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_mat[a-1][b-1] = 1
        adjacency_mat[b-1][a-1] = 1
    
    visited = [False] * N
    visited[0] = True 
    ans = 0 
    dfs_mat(0)
    print(ans)

Solution (Python):

def dfs(v):
    global adjacency_list, ans, visited
    
    if sum(visited) == N:
        ans += 1
        return
    for a in adjacency_list[v]:
        
        if visited[a] == True:
            continue
        
        else:
        
            visited[a] = True
            dfs(a)    
        
            visited[a] = False

if __name__ == "__main__":
    
    N, M = map(int, input().split())
    
    adjacency_list = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        adjacency_list[a-1].append(b-1)
        adjacency_list[b-1].append(a-1)
    
    visited = [False] * N
    visited[0] = True 
    ans = 0 
    dfs(0)
    print(ans)

Solution (Python):

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

route = [[] for i in range(N)]
for ai, bi in ab:
    route[ai - 1].append(bi - 1)
    route[bi - 1].append(ai - 1)


    
def walk(pos, footprint):
    
    if footprint == 2 ** N - 1: return 1
    
    
    ans = 0
    for to in route[pos]:
        if footprint & 2 ** to > 0: continue
        else: ans += walk(to, footprint + 2 ** to)
    return ans

print(walk(0, 1))

Solution (Python):
N, M = map(int, input().split())
result = 0
array = [[] for _ in range(N)]

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

def search(x, L):
    LL = list(L)
    global result
    LL.append(x)
    if len(LL) == N:
        result += 1
        return
    for i in range(len(array[x-1])):
        if not array[x-1][i] in L:
            search(array[x-1][i], LL)
        
def main():
    L = []
    search(1, L)
    print(result)

main()

Solution (Python):
def find_route(now, node, route):
    count = 0
    if min(node) == 1:
        return 1
    dist = route[now]
    for i in dist:
        if node[i] == 0:
            tmpnode = node.copy()
            tmpnode[i] = 1
            count += find_route(i, tmpnode, route)
    return count

(n, m) = list(map(int, input().split()))
route = {}
for i in range(m):
    (a, b) = list(map(int, input().split()))
    a -= 1
    b -= 1
    if a in route:
        route[a].append(b)
    else:
        route[a] = [b]
    if b in route:
        route[b].append(a)
    else:
        route[b] = [a]
count = find_route(0, [1] + [0 for _ in range(n - 1)], route)

print(count)

Solution (Python):
def dfs(v,N,visited):
    allvis=True
    for i in range(N):
        if visited[i]==False:
            allvis=False
    if allvis:
        return 1
    ret=0
    
    for i in range(N):
        if graph[v][i]==False:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ret+=dfs(i,N,visited)
        visited[i]=False
    return ret



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

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

print(dfs(0,N,visited))

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)
def dfs(V, v):
  _V = [v for v in V]
  _V[v] = 1
  cnt = 0
  if sum(_V) == N:
    return 1
  else:
    for adj in G[v]:
      if _V[adj] == 0:
        cnt += dfs(_V, adj)
    return cnt
print(dfs([0] * N, 0))

Solution (Python):

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

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

map_org = [[0 for _ in range(N)] for _ in range(N)]

for a, b in ab:
    map_org[a-1][b-1] = 1
    map_org[b-1][a-1] = 1

def dfs(v):
    visited[v] = 1
    if sum(visited) == N:
        return 1

    ret = 0    
    for i in range(N):
        if map_org[v][i] == 1:
            if visited[i] == 0:
                ret += dfs(i)
                visited[i] = 0
    return ret


visited = [0 for _ in range(N)]
print(dfs(0))

Solution (Python):
import itertools
N, M = map(int ,input().split())
matrix = [[0]*N for i in range(N)]

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

count = 0

for p in itertools.permutations(range(N)):
    
    if p[0] != 0:
        break
    check = 1
    for s in range(N-1):
        check = check  * matrix[p[s]][p[s+1]]
    count += check

print(count)

Solution (Python):
def solve(N, M, Es):
    al = {}
    for e in Es:
        al.setdefault(e[0], []).append(e[1])
        al.setdefault(e[1], []).append(e[0])

    ans = 0
    q = [(1, [1])]
    while len(q) > 0:
        current, history = q.pop()
        nexts = al[current] if current in al else []
        if len(history) == N:
            ans += 1
        for n in nexts:
            if n not in history:
                nhist = history[:]
                nhist.append(n)
                q.append((n, nhist))
    return ans


if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    Es = []
    for _ in range(M):
        Es.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, Es))

Solution (Python):

import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aData = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    def addPath(d,a,b):
        if a in d:
            d[a].add(b)
        else:
            d[a]={b}
    dT = {}
    for a,b in aData:
        addPath(dT,a,b)
        addPath(dT,b,a)

    def dfs(dT,iStart,iC):
        if len(dsVisited) == iN:
            iC += 1
            return iC
        for i in dT[iStart] - dsVisited:
            dsVisited.add(i)
            iC = dfs(dT,i,iC)
            dsVisited.remove(i)
        return iC

    dsVisited = {1}
    print(dfs(dT,1,0))
解()

Solution (Python):
from itertools import permutations
def inpl(): return [int(i) for i in input().split()]

N, M = inpl()
path = [[False]*N for _ in range(N)]


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

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

Solution (Python):
import itertools
N, M = map(int, input().split())
A = []
for i in range(M):
    a, b = map(int, input().split())
    A += [[a, b]]
L = list(range(2, N+1))
count = 0
for v in itertools.permutations(L):
    v = list(v)
    v.insert(0, 1)
    BOOL = 'T'
    i = 0
    while BOOL == 'T' and i < N-1:
        if sorted(v[i:i+2]) in A:
            i += 1
        else:
            BOOL = 'F'
    if BOOL == 'T':
        count += 1
print(count)

Solution (Python):
import sys
sys.setrecursionlimit(250010)

N, M =map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]
node=[0 for _ in range(N)]
node[0]=1
ans=0

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

    adj=[]
    for i in ab:
        if i[0]==v+1 and node[i[1]-1]==0:
            adj.append(i[1])
        if i[1]==v+1 and node[i[0]-1]==0:
            adj.append(i[0])
    for i in adj:
        node[i-1]=1
        dfs(i-1)
        node[i-1]=0
    return

dfs(0)
print(ans)

Solution (Python):
import itertools

n, m = [int(_) for _ in input().split(' ')]
edges = set()
for _ in range(m):
    a, b = [int(_) for _ in input().split(' ')]
    edges.add((a, b))
    edges.add((b, a))

answer = 0
for vertices in itertools.permutations(range(2, n + 1)):
    steps = [1] + list(vertices)
    if all([(steps[i], steps[i + 1]) in edges for i in range(n - 1)]):
        answer += 1
print(answer)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = map(int, raw_input().split())
edge = [[False] * N for i in range(N)]

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

def func(num, used):
    if not True in used:
        return 1
    ret = 0
    for i in range(N):
        if used[i] and edge[num][i]:
            used[i] = False
            ret += func(i, used)
            used[i] = True
    return ret

print func(0, [False] + [True] * (N - 1))

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

result = []
stack = []

def path(start, visited):
    if len(visited) >= N:
        result.append(visited[:])
        exit
    stack.append(start)
    if len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint not in visited:
            visited.append(nextpoint)
            for i in range(M):
                if A[i][0] == start:
                    path(A[i][1], visited)
                if A[i][1] == start:
                    path(A[i][0], visited)
            visited.pop()

path(1, [])
result = list(map(list, set(map(tuple, result))))
print(len(result))

Solution (Python):
import itertools

N,M=map(int,input().split())
link = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    link[a].add(b)
    link[b].add(a)
sqs = itertools.permutations(range(2,N+1))
ans = 0
for sq in sqs:
    v = 1
    success = 1
    for w in sq:
        if w in link[v]:
            v = w
        else:
            success = 0
            break
    ans += success
print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())
a = []
c = 0
for _ in [0]*m:
  a += [list(map(int,input().split()))]
for x in list(itertools.permutations(range(2,n+1))):
  y = [1] + list(x)
  f = True
  for i in range(1,n):
    if (not [y[i-1],y[i]] in a) and (not [y[i],y[i-1]] in a):
      f = False
      break
  if f:
    c += 1
print(c)

Solution (Python):
from itertools import permutations

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

adjM = [[0] * N for v in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adjM[a - 1][b - 1] = 1
    adjM[b - 1][a - 1] = 1


ans = 0
for vs in permutations(range(1, N)):
    vs = [0] + list(vs)
    for i in range(N - 1):
        if adjM[vs[i]][vs[i + 1]] == 0:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
def dfs(v, n, visited, g):
    if False not in visited:
        return 1

    result = 0

    for i in range(n):
        if not g[v][i]:
            continue
        if visited[i]:
            continue
        visited[i] = True
        result += dfs(i, n, visited, g)
        visited[i] = False

    return result


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

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

Solution (Python):
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

def tansaku(already, paths, cur, n):
    global ans
    aim = [i for i in paths[cur] if i not in already]
    
    if aim == []:
        if len(already) == n-1:
            
            ans += 1
        return

    for a in aim:
        tansaku(already+[cur], paths, a, n)

N, M = getNM()
paths = [[] for i in range(N)]
ans = 0
for i in range(M):
    a, b = getNM()
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

tansaku([], paths, 0, N)
print(ans)

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]

def dfs(V,s):
  V[s]=1
  if sum(V)==n:
    cnt[0]+=1
  else:
    for adj in edges[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())
a = []
b = []
ans = 0
for i in range(M):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

current_num = 1
fin_li = [1]
s_li = [[current_num,fin_li]]
while len(s_li) > 0:
    if len(s_li[0][1]) == N:
        ans += 1
    else:
        next_li = [b[i] for i, x in enumerate(a) if x == s_li[0][0]]
        next_li += [a[i] for i, x in enumerate(b) if x == s_li[0][0]]
        next_li = [[x, s_li[0][1]+[x]] for x in next_li if not x in s_li[0][1]]
        s_li += next_li
    s_li.pop(0)

print(ans)

Solution (Python):
N, M = map(int, input().split())
adjs = [list() for _ in range(N)]
vis = [False for _ in range(N)]

def dfs(v, cnt):
    if vis[v]:
        return 0
    vis[v] = True
    cnt += 1
    ka = 0
    for x in adjs[v]:
        ka += dfs(x, cnt)
    if cnt == N:
        ka = 1
    vis[v] = False
    return ka

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

Solution (Python):
import itertools

n,m = map(int,input().split())
graph = dict()
for i in range(1,n+1):
    graph[i] = []
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

t = [i for i in range(1,n+1)]
testcase = list(itertools.permutations(t))
counter = 0
for i in range(len(testcase)):
    if testcase[i][0] != 1:
        break
    else:
        temp = True
    now = 1
    for k in range(1,n):
        if testcase[i][k] not in graph[now]:
            temp = False
            break
        else:
            now = testcase[i][k]
    if temp:
        counter += 1

print(counter)

Solution (Python):
ans=0

def dfs(pos, open):
    if open.count(False)==len(arr):
        global ans
        ans+=1

    for i in range(2,N+1):
        if c[pos][i] and open[i]:
            open_next=open.copy()
            open_next[i]=False
            dfs(i, open_next)

N,M=map(int,input().split())
c=[[False for j in range(N+1)] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    c[a][b]=c[b][a]=True

arr=[True for i in range(N+1)]
arr[0]=arr[1]=False
dfs(1, arr)
print(ans)

Solution (Python):
from itertools import permutations
N, M = map(int, input().split())
E = [[False]*N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    E[a][b] = E[b][a] = True
ans = 0
for t in permutations(range(1, N)):
    pv = 0
    for v in t:
        if not E[pv][v]:
            break
        pv = v
    else:
        ans += 1
print(ans)

Solution (Python):
from itertools import permutations
 
N,M = map(int,input().split())
ans=0
s = []
 
for i in range(M):
    a,b = map(int,input().split())
    s.append([a,b])



t=list(permutations(list(range(1,N+1))))



for i in range(len(t)):
    flag=True
    if t[i][0]!=1: continue 
    for j in range(N-1):
        a=sorted([t[i][j],t[i][j+1]]) 
        
        
        
        if a not in s: flag=False
    if flag == True:
        ans = ans + 1

print(ans)

Solution (Python):
def DFS(Current_Node,Visited_Node):
    if len(Visited_Node) == N - 1:
        return 1
    ans = 0

    for a,b in AB:
        if a == Current_Node and b not in Visited_Node:
            vns = Visited_Node.copy()
            vns.add(a)
            ans += DFS(b, vns)

        if b == Current_Node and a not in Visited_Node:
            vns = Visited_Node.copy()
            vns.add(b)
            ans += DFS(a,vns)
    return ans



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

for i in range(M):
    a,b = map(int,input().split())
    AB.append((a,b))

ans = DFS(1,set())
print(ans)

Solution (Python):
def f(currentNode, visitedNodeSet):
    if len(visitedNodeSet) == N - 1:
        return 1
    sum = 0
    for a, b in AB:
        if (a == currentNode) and (b not in visitedNodeSet):
            vns = visitedNodeSet.copy()
            vns.add(a)
            sum += f(b, vns)
        if (b == currentNode) and (a not in visitedNodeSet):
            vns = visitedNodeSet.copy()
            vns.add(b)
            sum += f(a, vns)
    return sum


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

for i in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a, b))



print(f(1, set()))

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):
import itertools

n_m_input = list(map(int, input().split()))
n = n_m_input[0]
m = n_m_input[1]

all_point_string = ''.join([str(i+1) for i in range(n-1)])
path_string_list = list(itertools.permutations(all_point_string))

edge_list = [[0]*n for _ in range(n)]
counter = 0
answer = 0

for _ in range(m):
	edge = list(map(int, input().split()))
	edge_list[edge[0]-1][edge[1]-1] = 1
	edge_list[edge[1]-1][edge[0]-1] = 1

for path in path_string_list:
	counter = 0
	path_str = '0'+''.join(path)
	for i in range(n-1):
		if edge_list[int(path_str[i])][int(path_str[i+1])] == 1:
			counter += 1
	if counter == n-1:
		answer += 1

print(answer)

Solution (Python):
cnt = 0

def dfs(v, n, used, linked_list):
    global cnt
    if len(used) == n:
        cnt += 1
        return
    else:
        for next_v in linked_list[v]:
            if next_v not in used:
                used.append(next_v)
                dfs(next_v, n, used, linked_list)
                used.remove(next_v)
        return

def main():
    global cnt
    n, m = map(int, input().split())
    linked_list = [[] for _ in range(n+1)]
    for i in range(m):
        a, b = map(int, input().split())
        linked_list[a].append(b)
        linked_list[b].append(a)
    used = [1]
    dfs(1, n, used, linked_list)
    print(cnt)

if __name__ == '__main__':
    main()

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

Visited = [False for i in range(N)]
Visited[0] = True
ans = 0
def DFS(i):
    allvisited = True
    for j in range(N):
        if Visited[j] == False:
            allvisited = False
    if allvisited:
        return 1
    else:
        ret = 0
        for node in Edge[i]:
            if Visited[node] == False:
                Visited[node] = True
                ret += DFS(node)
                Visited[node] = False
        return ret

print(DFS(0))

Solution (Python):
import itertools

n, m = map(int, input().split())
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
ans = 0
for i in itertools.permutations(range(2, n + 1)):
    if not graph[0][i[0] - 1]:
        continue
    for j in range(n - 1):
        if j == n - 2:
            ans += 1
            break
        if not graph[i[j] - 1][i[j + 1] - 1]:
            break
print(ans)

Solution (Python):
import itertools

def sonzai(path, start, goal):
    for i in path:
        if start in i:
            if start > goal:
                if i[0] == goal:
                    return True
            else:
                if i[1] == goal:
                    return True
    return False

n, m = map(int, input().split())
path = []
for i in range(m):
    a, b = map(int, input().split())
    path.append([a, b])
ans = 0
for i in itertools.permutations(range(2, n + 1)):
    if not sonzai(path, 1, i[0]):
        continue
    for j in range(n - 1):
        if j == n - 2:
            ans += 1
            break
        if not sonzai(path, i[j], i[j + 1]):
            break
print(ans)

Solution (Python):


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

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

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

def search(v,edge,cl,count):
    come_list = cl[:]
    come_list[v-1]=1
    if sum(come_list)==N:
         return count+1
    else:
        for e in edge[v-1]:
            if come_list[e-1]==0:
                count=search(e,edge,come_list,count)
    return count
            
cl = [0 for i in range(N)]
print search(1,edge,cl,0)

Solution (Python):
N, M = map(int, input().split())
a = []
b = []
for i in range(M):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

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

for i in range(M):
    graf[a[i] - 1].append(b[i] - 1)
    graf[b[i] - 1].append(a[i] - 1)

cnt = 0

def sarch(v, graf_check):
    global cnt
    check = list(graf_check)
    check[v] = 1
    
    if sum(check) == N:
        cnt += 1
    else:
        for i in graf[v]:
            if graf_check[i] == 0:
                sarch(i, check)
                
sarch(0, [0 for i in range(N)])
print(cnt)