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:
n,m=map(int,input().split())
ab=[]
for i in range(m):
    ab.append(list(map(int,input().split())))

ans=0
def dfs(start,finish):
    global ans
    finish.add(start)#もう訪れたところ
   # print(finish)
    if len(finish)==n:#全部回ってたら終了
        ans+=1
        
    for i in adlist[start-1]:
        if i not in finish:#通ったところに入っていないなら通れるということ   
 #           print(i)
            dfs(i,finish)

adlist=[]
for h in range(n):    
    adlist.append([])
for j in range(m):
    x=ab[j][0]
    y=ab[j][1]
    adlist[x-1].append(y)
    adlist[y-1].append(x)
finish=set()
#print(adlist)
dfs(1,finish)#引数がけすノード
print(ans)

Submission status: Wrong Answer

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


import copy
def check(c):
  if len(c) != N-1:
    return False

  for k in range(2**len(c)):
    f=False
    cc=copy.deepcopy(c)
    for l in range(len(c)):
      if k>>l&1==1:
        tmp=cc[l][0]
        cc[l][0]=cc[l][1]
        cc[l][1]=tmp
    

    start_table = [0]*N
    end_table = [0]*N
    start = -1
    # end = -1
    # print(c)

    for l in cc:
      start_table[l[0]-1] += 1
      if start_table[l[0]-1] == 2:
        f=True
        break
    if f:
      continue
    
    
    for l in cc:
      end_table[l[1]-1] += 1
      if end_table[l[1]-1] == 2:
        f=True
        break
    if f:
      continue
    
    for i in range(len(cc)):
      if cc[i][0] == 1:
        start = i
      # if c[i][1]==N:
      #   end = i


    if start==-1:
      continue

    # if end == -1:
      # return False
      # pass
    # print(cc)
    return True


n=0
for i in range(2**M):
  c=[]
  for j in range(M):
    if i >> j & 1==1:
      c.append(m[j])
  if check(c):
    n += 1



print(n)

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
  a, b = map(lambda x:int(x)-1, input().split())
  graph[a] += [b]
  graph[b] += [a]

print(graph)

used = [0]*n
global ans 
ans = 0
def dfs(u):
  global ans
  used[u] = 1
  if sum(used) == n:
    ans += 1
    return 
  
  for v in graph[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(v)
      used[v] = 0 

  return 

dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:

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

used = [0]*n
global ans 
ans = 0
def dfs(u):
  global ans
  used[u] = 1
  if sum(used) == n:
    ans += 1
    return ans
  
  for v in graph[u]:
    if used[v] == 0:
      used[v] = 1
      dfs(u)
      used[v] = 0 

  return ans

dfs(0)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
ans=0
for v in permutations([int(i) for i in range(n)],n):
  for i in range(n-1):
    if not v[i+1] in g[v[i]]:
      break
  else:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
#print(g)
# 訪れたことがあるか
chk = [False for i in range(n)]

from collections import deque


def dfs(now, prev):
  global a
  global ans
    # 今いる頂点から行ける頂点を順に next に入れてループ
  for next in g[now]:
    if next != prev:
      if chk[next]:
        # 終了時の動作の決定
        if a == n*(n-1)/2:
          ans += 1
      else:
        chk[next] = True
        a += next
        #print(next,now)
        dfs(next, now)

a = 0
ans = 0
chk[0] = True
dfs(0,-1)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

tu = [[] for j in range(n+1)]

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

na = [i for i in range(2,n+1)]
ans = 0


print(permutations(na))
for nara in permutations(na):
    st = 1
    f = True
    for i in range(n-1):
        if not nara[i] in tu[st]:
            f = False
        st = nara[i]
    if f == True:

        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i > m:
                tmp *= S[p[i]][p[i+1]]
        ans += tmp

    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def resolve():
    n, m = map(int, input().split())
    S = [[0]*m for i in range(m)]

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

    ans = 0
    for p in itertools.permutations(range(n)):
        if p[0] != 0:
            break;
        tmp = 1
        for i, v in enumerate(p):
            if i > m:
                tmp *= S[p[i+1]][p[i+1]]
        ans += tmp

    print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
original_paths={}
paths={}
for n in range(1,N+1):
    original_paths[n]=[]
    paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)
    paths[s].append(e)
    paths[e].append(s)#以上地図作り
    
visited=[1]
current_point=1
answer=0

while len(paths[1])!=0:#すべてのルートを探索済み==点1から動けない
    print(current_point,visited,paths)
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:#next_pointに行ったことがある

            if len(paths[current_point])!=1:#next_point以外に選択肢がある
                paths[current_point].remove(next_point)#next_pointを選択肢から消す

            else:#next_point以外に選択肢がない(current_pointは行き止まり)
                if len(visited)==N:#すべての点を訪れたかチェック
                    answer+=1
                prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
                paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
                paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
                visited.remove(current_point)#current_pointをvisitedから除き、
                current_point=prior_point#prior_pointに戻る

        else:#next_pointに行ったことがない
            visited.append(next_point)#next_pointをvisitedに加え、
            current_point=next_point#next_pointに進む

    else:
        prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
        paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
        paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
        visited.remove(current_point)#current_pointをvisitedから除き、
        current_point=prior_point#prior_pointに戻る
        
print(answer)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
original_paths={}
paths={}
for n in range(1,N+1):
    original_paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)#以上地図(原本)作り
    
visited=[1]
current_point=1
answer=0
import copy
paths=copy.deepcopy(original_paths)

while len(paths[1])!=0:#すべてのルートを探索済み==点1から動けない
    print(current_point,visited,paths)
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:#next_pointに行ったことがある

            if len(paths[current_point])!=1:#next_point以外に選択肢がある
                paths[current_point].remove(next_point)#next_pointを選択肢から消す

            else:#next_point以外に選択肢がない(current_pointは行き止まり)
                if len(visited)==N:#すべての点を訪れたかチェック
                    answer+=1
                prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
                paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
                paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
                visited.remove(current_point)#current_pointをvisitedから除き、
                current_point=prior_point#prior_pointに戻る

        else:#next_pointに行ったことがない
            visited.append(next_point)#next_pointをvisitedに加え、
            current_point=next_point#next_pointに進む

    else:
        prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
        paths[current_point]=original_paths[current_point].copy()#current_pointからの選択肢を初期化
        paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
        visited.remove(current_point)#current_pointをvisitedから除き、
        current_point=prior_point#prior_pointに戻る
        
print(answer)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
original_paths={}
paths={}
for n in range(1,N+1):
    original_paths[n]=[]
    paths[n]=[]
for m in range(1,M+1):
    s,e=map(int,input().split())
    original_paths[s].append(e)
    original_paths[e].append(s)
    paths[s].append(e)
    paths[e].append(s)#以上地図作り
    
visited=[1]
current_point=1
answer=0

while len(paths[1])!=0:#すべてのルートを探索済み==点1から動けない
    if len(paths[current_point])!=0:
        next_point=paths[current_point][0]
    
        if next_point in visited:#next_pointに行ったことがある

            if len(paths[current_point])!=1:#next_point以外に選択肢がある
                paths[current_point].remove(next_point)#next_pointを選択肢から消す

            else:#next_point以外に選択肢がない(current_pointは行き止まり)
                if len(visited)==N:#すべての点を訪れたかチェック
                    answer+=1
                prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
                paths[current_point]=original_paths[current_point]#current_pointからの選択肢を初期化
                paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
                visited.remove(current_point)#current_pointをvisitedから除き、
                current_point=prior_point#prior_pointに戻る

        else:#next_pointに行ったことがない
            visited.append(next_point)#next_pointをvisitedに加え、
            current_point=next_point#next_pointに進む

    else:
        prior_point=visited[-2]#ひとつ前にいた点をprior_pointとし、
        paths[current_point]=original_paths[current_point]#current_pointからの選択肢を初期化
        paths[prior_point].remove(current_point)#prior_pointの選択肢からcurrent_pointを除く
        visited.remove(current_point)#current_pointをvisitedから除き、
        current_point=prior_point#prior_pointに戻る
        
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n, m = map(int, input().split())
  #隣接リストを作る
  path = [[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
    path[a][b] = True
    path[b][a] = True
  ans = 0
  for i in permutations(range(n), n):
    if i[0] == 1:
      for j in range(n):
        if j == n-1:
          ans += 1
          break
        if not path[i[j]][i[j+1]]:
          break
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
r = list(range(1,N+1))
ok = 1
cnt = 0
for v in itertools.permutations(r):
    if(v[0] == 1):
        ok = 1
        for i in range(N-1):
            if(list(v[i:i+2]) not in ab and list(reversed(v[i:i+2])) not in ab):
                ok = 0
                break
        print(ok,v)
        if(ok == 1):
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
N, M = map(int, input().split())
A = [[0]* N for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    A[a-1][b-1] = 1
    A[b-1][a-1] = 1
visited=[1]+[0]*(N-1)
def DFS(now, visited):
    ans = 0
    if not 0 in visited:
        return 1
    for i in range(N):
        if A[now][i] == 0:
            return
        if visited[i] == 1:
            return
        visited[i] = 1
        ans += DFS(i, visited)
        visited[i] = 0
    return ans
print(DFS(0, visited))

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]

vistedvisited = [[]]
cnt = 0
for i in itertools.permutations(ab, n):
    start = 1
    visited = [1]
    for j in i:
        if j[0] == start and not j[1] in visited:
            start = j[1]
            visited.append(j[1])
        if j[1] == start and not j[0] in visited:
            start = j[0]
            visited.append(j[0])
    if len(visited) == n and len(vistedvisited) == 0:
        vistedvisited.append(visited)
        cnt += 1
    if len(visited) == n and not visited in vistedvisited:
        vistedvisited.append(visited)
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools

n,m=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(m)]
v=list(itertools.permutations(range(1,n+1)))
print(v)

ans=0

for x in v:
    tf=True
    if x[0]!=1:
        tf=False
    else:
        for i in range(n-1):
            if not ([x[i],x[i+1]] in g or [x[i+1],x[i]] in g):
                tf=False
                break
    if tf:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M=map(int,list(input().split(" ")))
E_list=[]
for i in range(M):
    p,q=map(int,list(input().split(" ")))
    E_list.append([[p,q]])
def comb(E,m):
    n=len(E)
    if m==0:
        return [[]]
    elif n==m:
        sum=[]
        for i in range(n):
            sum+=E[i]
        return [sum]
    elif n<m:
        return [[]]
    else:
        lis1=E[:-1]
        sum=comb(lis1,m)
        lis2=comb(lis1,m-1)
        k=len(lis2)
        for i in range(k):
            sum.append(lis2[i]+E[-1])
        return sum
K=comb(E_list,N-1)
k=len(K)
s=0
for i in range(k):
    k_list=K[i]
    m=len(k_list)
    E=defaultdict(lambda:0)
    for j in range(m):
        E[k_list[j][0]]+=1
        E[k_list[j][1]]+=1
    if E[1]!=1:
        continue
    x1=0
    x2=0
    for j in range(2,N+1):
        if E[j]==1:
            x1+=1
        if E[j]==2:
            x2+=1
    if x1!=1 or x2!=N-2:
        continue
    else:
        s+=1
print(s)

Submission status: Wrong Answer

Solution code:
def dfs(i):
  global count
  global seen
  global G

  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] == 0

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

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

Submission status: Wrong Answer

Solution code:
def dfs(i):
  global count
  global seen
  global G

  print(seen)
  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] == 0

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

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

Submission status: Wrong Answer

Solution code:
def dfs(i):
  global count
  global seen
  global G

  end = True
  for n in range(N):
    if seen[n] == 0 and n != i:
      end = False

  if (end):
    count += 1
    return

  seen[i] = 1
  for g in G:
    if g[0] == i:
      if seen[g[1]] == 1:
        continue
      dfs(g[1])
  
  for g in G:
    if g[1] == i:
      if seen[g[0]] == 1:
        continue
      dfs(g[0])

  seen[i] == 0

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

G = []

for i in li:
  G.append([i[0]-1, i[1]-1])

count = 0
seen = [0] * N
dfs(0)

print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
#dc={}
lc=[[] for _ in range(N)]#インデは-1、要素はそのまま
for i in range(M):
    a,b=map(int,input().split())
    lc[a-1].append(b)
    lc[b-1].append(a)
st=[1]
df={1:1}
ans=0
while st:
    tmp=st.pop()
    if len(df)==N:
        ans+=1
        del df[tmp]
    for c in lc[tmp-1]:
        if not c in df:
            st.append(c)
            df[c]=1
print(ans)

Submission status: Wrong Answer

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

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(a, []).append(b)
    d.setdefault(b, []).append(a)

l = sorted(d.items())

# print(d)
def dfs(v, c):
    if visited[v-1]: return 0
    visited[v-1] = True
    if False not in visited:
        c += 1
    
    # print(visited, False not in visited, c)
    
    # print('vertex', v)
    
    for next_v in d[v]:
        c += dfs(next_v, c)
    
    return c

c = 0
ans = 0
for i in l[0][1]:
    ans += dfs(i, c)
    
print(ans)

Submission status: Wrong Answer

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

def dfs(now,depth):
    if visited[now]==1:
        return 0
    elif depth==n-1:
        return 1
    else:
        visited[now]=1
        total=0
        for i in range(n):
            if paths[now][i]==1:
                total+=dfs(i,depth+1)
                print(total)
        visited[now]=0
        return total

print(dfs(0,0))

Submission status: Wrong Answer

Solution code:
import itertools
import copy

n, m = map(int, input().split())
List = [list(map(int, input().split())) for i in range(m)]
check = [0 for _ in range(n)]
res = 0

def all_1(res_list):
    leng = len(res_list)
    for i in range(leng):
        if res_list[i] == 0:
            return False
    return True

def coo(i, check):
    global res
    b = copy.deepcopy(check)
    if b[i-1] == 0:
        b[i-1] = 1
        if all_1(b):
            res += 1
        length = len(List)
        for j in range(length):
            if List[j][0] == i:
                coo(List[j][1], b)
        
        
coo(1, check)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [[False]*(N+1) for _ in range(N+1)]
for i in l:
    graph[i[0]][i[1]] = True
    graph[i[1]][i[0]] = True

visited = [0]*(N+1)

stack = deque([1])
visited[1] = 1
cnt = 0
while stack:
    g = stack.pop()
    if min(visited[1:]) == 1:
        visited[g] = 0
        cnt += 1
    for i in range(1, N+1):
        if graph[g][i] and visited[i] == 0:
            visited[i] = 1
            stack.append(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
nmax = 8
graph = np.array([[False]*nmax]*nmax)

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

def dfs(v, n, visited): # v：今訪れた頂点
    all_visited = True
    for i in range(n):
        if visited[i] == False:
            all_visited = False

    if all_visited:
        return 1 #1通り
    
    ret = 0 #最初は0通り
    
    for i in range(n):
        if graph[v][i] == False: #vからiに行けない場合は除外
            continue
        if visited[i]: #iを訪問済みだったら行かない
            continue
        
        visited[i] = True #vからiに訪問
        ret += dfs(i, n, visited) #今iにいる時の次の動作
        visited[i] = False #iではないところにいくケース
        
    return ret
  
dfs(0, n, visited)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n,m=map(int,input().split())
g=[[]for i in range(n)]; ans=0
for i in range(m):
  a,b=map(int,input().split())
  a-=1; b-=1
  g[a].append(b)
  g[b].append(a)
# print(g)
def dfs(x,visited):
  global ans
  # print(x,visited)
  for p in g[x]:
    if visited[p]==0:
      visited[p]=1
      if visited.count(1)==n:
        ans+=1
        # print(ans)
        return
      dfs(p,visited)
      visited[p]=0
v=[0]*n
v[0]=1
dfs(0,v)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

P = N-1
count = 0
for path in itertools.permutations(ab, P):
  flag = True
  prev = 1
  memo = [0]*N
  for i in range(P):
    memo[prev-1] = 1
    if flag == True:
      if path[i][0] == prev:
        prev = path[i][1]
      elif path[i][1] == prev:
        prev = path[i][0]
      else:
        flag = False
        continue
      if i == P-1:
        count += 1
      if memo[prev-1] == 1:
        flag = False
        
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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

P = N-1
count = 0
for path in itertools.permutations(ab, P):
  flag = True
  prev = 1
  for i in range(P):
    if flag == True:
      if path[i][0] == prev:
        prev = path[i][1]
      elif path[i][1] == prev:
        prev = path[i][0]
      else:
        flag = False
        continue
      if i == P-1:
        print(path)
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
import itertools


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

ans = 0
node = list(range(1, N+1))
for x in itertools.permutations(node):
    for i in range(N-1):
        if not edge[x[i]][x[i+1]]:
            break
    else:
        ans += 1

print(ans // 2)#逆順が含まれるので半分

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
ab = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
cand = [[0]+[one] for one in ab[0]]
while len(cand)>0:
    tmp_cand = []
    for c in cand:
        last = c[-1]
        n = []
        for nc in ab[last]:
            if nc not in c:
                n.append(c+[nc])
        tmp_cand.extend(n)
    cand = tmp_cand
    if len(cand)>0 and len(cand[0])==N:
        break
print(len(cand))

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
ab = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
    
cand = [[0]+[one] for one in ab[0]]
while len(cand)>0:
    tmp_cand = []
    for c in cand:
        last = c[-1]
        n = []
        for nc in ab[last]:
            if nc not in c:
                n.append(c+[nc])
        tmp_cand.extend(n)
    cand = tmp_cand
    if cand!=[] and len(cand[0])==N:
        break
print(len(cand))

Submission status: Wrong Answer

Solution code:
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
import itertools 
count=0
for i in itertools.permutations(range(N)):
    if i[0]==0:
        result=1
        for j in range(N-1):
            result*=matrix[i[j]][i[j+1]]
            if result==1:
                count+=1
    else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
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
import itertools 
count=0
for i in itertools.permutations(range(N)):
    if i[0]==0:
        for j in range(N-1):
            result=1
            result*=matrix[i[j]][i[j+1]]
            if result==1:
                count+=1
    else:
        break
print(count)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,set([1])]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:
        if not p in visited:
            if len(visited)+1==N:
                count+=1

            else:
                a=visited
                a.add(p)
                stack.append([p,a])
print(count)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,set()]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:
        if not p in visited:
            if len(visited)+1==N:
                count+=1

            else:
                a=set(list(visited))
                a.add(p)
                stack.append([p,a])
print(count)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)

count=0
stack=[[1,set()]]
while stack:
    point,visited=stack.pop()
    for p in data[point]:
        if not p in visited:
            if len(visited)+1==N:
                count+=1

            else:
                a=visited
                a.add(p)
                stack.append([p,a])
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
node=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=[int(x)-1 for x in input().split()]
  node[a][b]=1
ct=0
for order in itertools.permutations(range(n),n):
  if order[0]==0:
    for j in range(n-1):
      if node[order[j]][order[j+1]]!=1:
        break
    ct+=1
print(ct)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(1000000000)

def dfs(start, paths, total, usedIndices):
    if total <= 1:
        return 1
    
    indices = findNodeIndex(start, paths, usedIndices)
    if len(indices) == 0:
        return 0

    count = 0
    for i in indices:
        nextNode = paths[i][1] if paths[i][0] == start else  paths[i][0]
        count += dfs(nextNode, paths, total - 1, usedIndices + [i])
    return count

def findNodeIndex(node, paths, usedIndices):
    return [i for (i, row) in filter(lambda x: (not x[0] in usedIndices) and (x[1][0] == node or x[1][1] == node), [(i, row) for i, row in enumerate(paths)])]

N, M = map(int, input().split())
PATHS = [list(map(int, input().split())) for _ in range(M)]
#start = findNodeIndex(1, PATHS)

print(dfs(1, PATHS, N, []))

Submission status: Wrong Answer

Solution code:
import sys
import copy
sys.setrecursionlimit(1000000000)

def dfs(start, paths, total):
    if total <= 1:
        return 1
    
    indixies = findNodeIndex(start, paths)
    if len(indixies) == 0:
        return 0

    count = 0
    for i in indixies:
        nextNode = paths[i][1] if paths[i][0] == start else  paths[i][0]
        newPaths = copy.deepcopy(paths)
        newPaths.pop(i)
        count += dfs(nextNode, newPaths, total - 1)
    return count

def findNodeIndex(node, paths):
    return [i for (i, row) in filter(lambda x: x[1][0] == node or x[1][1] == node, [(i, row) for i, row in enumerate(paths)])]

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

print(dfs(1, PATHS, N))

Submission status: Wrong Answer

Solution code:
import sys
import copy
from queue import Queue
sys.setrecursionlimit(1000000000)

def dfs(start, paths, count):
    if count <= 1:
        return 1
    
    indixies = findNodeIndex(start, paths)
    if len(indixies) == 0:
        return 0
    count = 0
    for i in indixies:
        nextNode = paths[i][1] if paths[i][0] == start else  paths[i][0]
        newPaths = copy.deepcopy(paths)
        newPaths.pop(i)
        count += dfs(nextNode, newPaths, count - 1)
    return count

def findNodeIndex(node, paths):
    return [i for (i, row) in filter(lambda x: x[1][0] == node or x[1][1] == node, [(i, row) for i, row in enumerate(paths)])]

N, M = map(int, input().split())
PATHS = [list(map(int, input().split())) for _ in range(M)]
#start = findNodeIndex(1, PATHS)

print(dfs(1, PATHS, N))