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.



Sample input:
3 3
1 2
1 3
2 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n, m= map(int, input().split())
a_list = []
b_list = []

for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
count = 0
for x in range(m):
    for j in range(m):
        route = [dict() for _ in range(n)]
        for i in range(m):
            if i == j or i == x:
                continue
            a, b = a_list[i]-1, b_list[i]-1
            route[a][b] = 1
            route[b][a] = 1

        di, _ = Dijkstra(route, 0).execute()
        if max(di) == n-1:
            count+=1

print(count)

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

n, m= map(int, input().split())
a_list = []
b_list = []

for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
count = 0
for j in range(m):
    route = [dict() for _ in range(n)]
    for i in range(m):
        if i == j:
            continue
        a, b = a_list[i]-1, b_list[i]-1
        route[a][b] = 1
        route[b][a] = 1

    di, _ = Dijkstra(route, 0).execute()
    if max(di) == n-1:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
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[s]=1
  V_c=V[:]
  if sum(V_c)==n:
    cnt+=1
  else:
    for v in edges[s]:
      if V_c[v]==0:
        dfs(V_c,v)
dfs(V,0)
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


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

# 普通にdfsで行けるイメージなのでそれをする
# パスの数を返す
def dfs(node, visited_list):
    paths = 0
    #debug_print(node)
    #debug_print(visited_list)
    visited = copy.copy(visited_list)
    if len(visited) == N:
        return 1
    for to in graph[node]:
        if to not in visited:
            visited.append(to)
            paths += dfs(to, visited)
    return paths

print(dfs(0, [0]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


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

# 普通にdfsで行けるイメージなのでそれをする
# パスの数を返す
def dfs(node, visited_list):
    paths = 0
    visited = copy.copy(visited_list)
    visited.append(node)
    if len(visited) == N:
        return 1
    for to in graph[node]:
        if to not in visited:
            paths += dfs(node, visited)
    return paths

print(dfs(0, [0]))

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
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))


# Binary converter
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


# Width First Search (+ Distance)
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


# Depth First Search (+Distance)
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)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
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))


# Binary converter
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


# Width First Search (+ Distance)
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


# Depth First Search (+Distance)
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_ = past_nodes[:]
            past_nodes_.append(next_node_i)
            dfs(next_node_i, past_nodes_, depth+1)
    

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)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
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))


# Binary converter
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


# Width First Search (+ Distance)
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


# Depth First Search (+Distance)
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_ = past_nodes
            past_nodes_.append(next_node_i)
            dfs(next_node_i, past_nodes_, depth+1)
    

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)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
# dfsで解く
def dfs(v, visited):
    global adjacency_list, ans
    # copy
    visited_copy = visited[:]
    print("v;%d" % v)
    print(visited)
    # 今いる場所を訪問済みにする
    visited_copy[v] = True
    for a in adjacency_list[v]:
        # 全部訪れたかどうか
        if sum(visited_copy) == N:
            ans += 1
            continue
        # 訪れたことがあるなら何もしない
        if visited[a] == True:
            continue
        # 訪れたことがないなら
        else:
        # 訪れたことにする
            visited_copy[a] = True
            dfs(a, visited_copy)    
        # 頂点aを未訪問にする
            visited_copy[a] = False

if __name__ == "__main__":
    # input
    N, M = map(int, input().split())
    # 隣接listを作る
    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
    print(visited)
    ans = 0 # 答え
    dfs(0, visited)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
N,M = map(int, input().split())
path = []
for _ in range(M):
    ai, bi = map(int, input().split())
    path.append((ai, bi))
    path.append((bi, ai))
    
ans = 0
def dfs(v, visited):
    # v: now here
    # visited: set
    global ans
#     print(visited)
    if v in visited:
        return
    else:
        visited.add(v)
        
    if len(visited)==N:
        ans += 1
        
    for pi in path:
        a,b = pi[0], pi[1]
        if a==b==v:
            dfs(a, visited)
        else:
            if a==v: dfs(b, visited)
            if b==v: dfs(a, visited)


dfs(1, set([]))
loop = 0
for pi in path:
    a,b = pi[0], pi[1]
    if a==b:
        loop += 1
print(ans+loop)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
N,M = map(int, input().split())
path = []
for _ in range(M):
    ai, bi = map(int, input().split())
    path.append((ai, bi))
    path.append((bi, ai))
    
ans = 0
def dfs(v, visited):
    # v: now here
    # visited: set
    global ans
    print(visited)
    if v in visited:
        return
    else:
        visited.add(v)
        
    if len(visited)==N:
        ans += 1
        
    for pi in path:
        a,b = pi[0], pi[1]
        if a==b==v:
            dfs(a, visited)
        else:
            if a==v: dfs(b, visited)
            if b==v: dfs(a, visited)


dfs(1, set([]))
loop = 0
for pi in path:
    a,b = pi[0], pi[1]
    if a==b:
        loop += 1
print(ans+loop)

Submission status: Wrong Answer

Solution code:
def search(x, visited):
    global ans, list_v
    visit_copy = visited[:]
    for v in list_v[x]:
        if visit_copy[v] == True:
            continue
        else:
            visit_copy[v] = True
            if sum(visit_copy) == N:
                ans += 1
                continue
            else:
                search(v, visit_copy)

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

Submission status: Wrong Answer

Solution code:
def lensetlist(A):
    B = []
    for i in A:
        if i not in B:
            B.append(i)
    return len(B)

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

for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
for i in range(M):
    A.append(B[i])
    B.append(A[i])
print(A)
print(B)
used = [0 for i in range(N)]
result = []
stack = []
ans = 0
def path(start, visited):
    if len(visited) == N:
        result.append(visited[:])
        exit
    stack.append(start)
    while len(stack) > 0:
        nextpoint = stack.pop()
        if nextpoint in visited:
            continue
        visited.append(nextpoint)
        for i in range(2*M):
            if A[i] == start:
                path(B[i], visited)
        visited.pop()

path(1, [])
print(lensetlist(result))

Submission status: Wrong Answer

Solution code:
def setlist(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if len(A) > i and len(A) > j:
                if A[i] == A[j]:
                    A.pop(j)

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

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

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

path(1, [])
setlist(result)
print(len(result))

Submission status: Wrong Answer

Solution code:
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()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [0 for i in range(n)]
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1] += 1
  lis[b-1] += 1
print(min(lis))

Submission status: Wrong Answer

Solution code:
import copy

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

class Node:
    def __init__(self, id):
        self.id = id
        self.path = []
        self.passed = False
    def __str__(self):
        return "id: " + str(self.id) + " path: " + str(self.path) + " passed: " + str(self.passed)

nodes = []
for i in range(N):
    nodes.append(Node(i))

for i in range(M):
    from_id, to_id = [ int(x) - 1 for x in input().split()]
    nodes[from_id].path.append(to_id)
    nodes[to_id].path.append(from_id)

def if_all_passed(nodes_current):
    for node in nodes_current:
        if not node.passed:
            return False
    return True

def go_child(id_new, nodes_current):
    print(id_new, nodes_current[0])
    nodes_current[id_new].passed = True
    if if_all_passed(nodes_current):
        return 1

    count = 0
    for i in nodes[id_new].path:
        if not nodes_current[i].passed:
            count += go_child(i, copy.deepcopy(nodes_current))
    return count

count = go_child(0, nodes)
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
graph=[[False for _ in range(n)] for _ in range(n)]
visited=[False for _ in range(n)]
visited[0]=True

for x in ab:
    graph[x[0]-1][x[1]-1]=True

def dfs(v,ret,n,visited):
    all_visited=True
    for i in range(n):
        if visited[i]==False:
            all_visited=False
    if all_visited:
        return 1
    for i in range(n):
        if graph[v][i]==False:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ret+=dfs(i,ret,n,visited)
        visited[i]=False
    return ret
print(dfs(0,0,n,visited))

Submission status: Wrong Answer

Solution code:

n, m = list(map(int, input().split()))
array = [[0]*n for _ in range(n)]
for i in range(m):
    ai, bi = list(map(int, input().split()))
    array[ai-1][bi-1] = 1
    array[bi-1][ai-1] = 1

#print(array)
dp = [[-1]*n for _ in range(n)]

def f(i,j):
    if j == 0:
        return 1
    if len(array[i]) == 1 and i != 1:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    dp[i][j] = sum([f(bi,j-1) for bi in array[i] if bi != 0])
    return dp[i][j]

print(f(0,n-2))

Submission status: Wrong Answer

Solution code:
import itertools
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
c = list(itertools.permutations(range(2,n+1), n-1))
ans = 0
for i in c:
  if i[0] not in l[1]:
    continue
  else:
    for j in range(1,len(i)):
      if i[j] not in l[i[j-1]]:
        break
      if j == len(i)-1:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m = map(int,input().split())
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
l = [[] for i in range(n+1)]
for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])
c = list(itertools.permutations(range(2,n+1), n-1))
ans = 0
for i in c:
  if i[0] not in l[1]:
    continue
  else:
    for j in range(1,len(i)):
      if i[j-1] not in l[i[j]]:
        break
      if j == len(i)-1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


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

lines = defaultdict(set)

for i in range(M):
	a,b = list(map(int,input().split())) #a -> b コスト:c の経路
	lines[a].add(b)
	lines[b].add(a)

ans = 0

def check(n,edtb):
	global ans

	if len(edtb) == N:
		ans += 1
		return

	for t in lines[n]:
		if not t in edtb:
			edtb.append(t)
			check(t,edtb)

for n in lines[1]:
	edtb = [1,n]
	check(n,edtb)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
 
n,m=map(int,input().split())
es=set()
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    es|={(u,v),(v,u)}

Submission status: Wrong Answer

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

moto_city = [i+2 for i in range(N-1)]
rout = [[0 for i in range(N+1)] for j in range(N+1)]

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

def check(a,b,city): #x to y
	global ans
	if rout[a][b] == 1:
		city.remove(b)
		if city:
			for j in city:
				check(b,j,city)
		else:
			ans += 1
		
	else:
		return

ans = 0
		
for i in range(2,N+1):
	city = moto_city[:]
	check(1,i,city)
	
print (ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
from collections import defaultdict

counter = 0

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

visited = []
def h(a,c=0):
    global counter
    if not a in visited: visited.append(a)
    else: 
        if c == N:
            counter += 1
        return
    c += 1
    for i in g[a]:

        h(i,c)
h(1)
print(counter)

Submission status: Wrong Answer

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

H = [[0 for _ in range(n)] for _ in range(n) ]
edge_list = []

for _ in range(m):
    a, b = map(int,input().split())
    edge_list.append([a,b])
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0
l[0] = 1

def dfs(node,x):
    
    visited = x
    global ans
    visited[node] = 1
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)



dfs(0,l)
print(ans)

Submission status: Wrong Answer

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

H = [[0 for _ in range(n)] for _ in range(n) ]
edge_list = []

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

def dfs(node):
    global ans
    visited[node] = 1
    for node_,edge_ in enumerate(H[node]):
        if edge_ == 1:
            if visited[node_] == 1:
                continue
            dfs(node_)
            if visited.count(0) == 0:
                ans += 1
            
ans = 0
dfs(0)
print(ans)