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 math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M=LI()
AB=[LI() for i in range(M)]
ans=0
L = list(itertools.permutations(range(2,M)))
#print(L)
for l in L:
	for lidx in range(len(l)):
		if lidx == 0:
			if [1,l[lidx]] not in AB:
				break
			continue
			
		if lidx == len(l)-1:
			if [l[lidx], N] not in AB:
				break
			continue
		
		if [l[lidx-1],l[lidx]] not in AB:
			break
	else:
		ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M=LI()
AB=[LI() for i in range(M)]
ans=0
L = list(itertools.permutations(range(2,M+1)))
#print(L)
for l in L:
	for lidx in range(len(l)):
		if lidx == 0:
			if [1,l[lidx]] not in AB and [l[lidx],1] not in AB:
				break
			continue
	
		if [l[lidx], l[lidx-1]] not in AB and [l[lidx-1],l[lidx]] not in AB:
			break
	else:
		ans+=1
print(ans)

Submission status: Wrong Answer

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

ans = 0

def dfs(v=0,d=0):
    if d == N-1:
        global ans
        ans += 1
        return
    for nv, bit in enumerate(ad[v]):
        if bit == 0: continue
        ad[v][nv] = 0
        ad[nv][v] = 0
        dfs(nv,d+1)
        ad[v][nv] = 1
        ad[nv][v] = 1

dfs()
print(ans)

Submission status: Wrong Answer

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

ans = 0

def dfs(v=0,d=0):
    if d == N-1:
        global ans
        ans += 1
    for nv, bit in enumerate(ad[v]):
        if bit == 0: continue
        ad[v][nv] = 0
        ad[nv][v] = 0
        dfs(nv,d+1)
        ad[v][nv] = 1
        ad[nv][v] = 1

dfs()
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import collections

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

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

cnt = 0

for i in itertools.combinations(a, (n - 1)):
    li = list(itertools.chain(*i))
    li.append(1)
    c = collections.Counter(li)
    if c.most_common()[0][1] == 2 and c.most_common()[-2][1] == 2 and c.most_common()[-1][1] == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

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


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

stack = [1]
visited = [[1]]
ans = 0

while stack:
    p = stack.pop()
    v = visited.pop()
    for i in range(n):
        if line[p][i]:
            if i not in v:
                if len(v) == n-1:
                    ans += 1
                else:
                    stack.append(i)
                    v.append(i)
                    visited.append(v)
print(ans)

Submission status: Wrong Answer

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

X=[[] for _ in range(n)]

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

print(X)

path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

Submission status: Wrong Answer

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

X=[[] for _ in range(n)]

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

print(X)

path=[i for i in range(2,n+1)]

visited=[1]+[0]*(n-1)

def dfs(v):
    if visited==[1]*n:
        return 1
    res=0
    for x in X[v]:
        if visited[x]==0:
            visited[x]=1
            print(visited)
            res+=dfs(x)
            visited[x]=0
    return res

print(dfs(0))

Submission status: Wrong Answer

Solution code:
import itertools

def is_edge_exists(node1, node2, edges):
	for edge in edges:
		if node1 in edge and node2 in edge:
			return True
	return False

def route_count(route, edges):
	if route[0]==1:
		return 0
	for i in range(len(route)-1):
		if not is_edge_exists(route[i], route[i+1], edges):
			return 0
	return 1

N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]
nodes = [i+1 for i in range(N)]
routes = list(itertools.permutations(nodes))

ans = 0
for route in routes:
	ans += route_count(route, edges)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

ans=0
G=[[False for i in range(8)]for i in range(8)]

def dfs(v,n,visi):
    allv=True

    for i in visi:
        if not i:
            allv=False

    if allv:
        return 1

    ret=0

    for i in range(n):
        if G[v][i]==False:
            continue
        if visi[i]:
            continue
        visi[i]=True
        ret+=dfs(i,n,G)
        visi[i]=False

    return ret

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

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

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

visi[0]=True

print(dfs(0,n,visi))

Submission status: Wrong Answer

Solution code:
#始点と終点は決まっていないので、軸優先や、深さ優先では手間が増えそう(これらは根っこのようなものがあるので)
#順列を使ってといて見ようと思う
#あ、、、始点決まってたわ()終点は決まってないですね。まあ、DFSやBFSでもできるけども。O(n^2)よりはO(n!)の方が小さい
from itertools import permutations

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

for vertexs in permutations(V):
    #print(vertexs)
    if vertexs[0] != 1:
        continue
    one_strike = False#一筆描きできるならTrue
    for vertex_index in range(len(vertexs)-1):
        for i in range(M):
            a,b = E[i]
            if (a == vertexs[vertex_index] and b == vertexs[vertex_index+1]) or (a == vertexs[vertex_index+1] and b == vertexs[vertex_index]):
                one_strike = True
                break
        if not one_strike :
            break
    if one_strike:
        one_strike_cnt += 1

print(one_strike_cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = [[False for i in range(N)] for j in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    L[a-1][b-1] = True
    L[b-1][a-1] = True
    
def dfs(x):
    global check
    check[x] += 1
    for i in range(N):
        if L[x][i] == True:
            L[x][i] = False
            dfs(i)
            
check = [0 for i in range(N)]
dfs(0)
print(min(check))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(n)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split());a=[[],[]];ans=0
for i in range(m):aa,bb=map(int,input().split());a[0].append(aa);a[1].append(bb)
def d(n,nl,ml):
  if sorted(nl+[n])==[i+1for i in range(m)]:return 1
  if n in nl:return 0
  l=len(ml[0]);ans=0
  for i in range(l):
    c=[ml[0][:i]+ml[0][i+1:],ml[1][:i]+ml[1][i+1:]]
    if ml[0][i]==n:ans+=d(ml[1][i],nl+[n],c)
    if ml[1][i]==n:ans+=d(ml[0][i],nl+[n],c)
  return ans
for i in range(m):
  if a[0][i]==1:
    c=[a[0][:i]+a[0][i+1:],a[1][:i]+a[1][i+1:]]
    ans+=d(a[1][i],[1],c)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(l,now):
    global ans
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        print(i)
        if l[i] == 0:
            l[i] += 1
            now = i
            dfs(l,now)
            l[i] -= 1
        else:
            continue
dfs(l,1)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy 
N,M = map(int,input().split())
dict = {}
for m in range(M):
    a,b = map(int,input().split())
    if a in dict:
        dict[a].append(b)
    else:
        dict[a] = [b]
    if b in dict:
        dict[b].append(a)
    else:
        dict[b] = [a]
ans = 0
l = [0 for i in range(N+1)]
l[1] = 1
def dfs(l,now):
    global ans
    ll = copy.deepcopy(l)
    if sum(l) == N:
        ans += 1
        return(0)
    for i in dict[now]:
        if l[i] == 0:
            ll[i] += 1
            now = i
            dfs(ll,now)
        else:
            continue
dfs(l,1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
neighbor_graph = [[False] * N for _ in range(N)]
for _ in range(M):
  a, b = map(int, raw_input().split())
  neighbor_graph[a - 1][b - 1] = True
  neighbor_graph[b - 1][a - 1] = True

def find(now, checked):
  if len(checked) == N:
    return 1
  res = 0
  for i in set(range(N)) - checked:
    if neighbor_graph[now][i]:
      res += find(i, checked | {i})
  return res

res = 0
for i in range(N):
  res = max(res, find(i, {i}))
print res

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)
    # G[k] = list(set(G[k]))
    # G[v] = list(set(G[v]))

count = 0
visited = []
visited.append(1)
history = []


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        if visited not in history:
            count += 1
            history.append(visited)
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            dfs(graph, label, visited)
            visited = visited[0:-2]


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)
    # G[k] = list(set(G[k]))
    # G[v] = list(set(G[v]))

count = 0
visited = []
visited.append(1)
history = []


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        print(visited)
        if visited not in history:
            count += 1
            history.append(visited)
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            dfs(graph, label, visited)
            visited = visited[0:-2]


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)
    # G[k] = list(set(G[k]))
    # G[v] = list(set(G[v]))

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            dfs(graph, label, visited)
            visited.pop(-1)


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)
    G[k] = list(set(G[k]))
    G[v] = list(set(G[v]))

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
        return visited
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            visited = dfs(graph, label, visited)
            visited.pop(-1)
    return visited


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
        return visited
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            visited = dfs(graph, label, visited)
            visited.pop(-1)
    return visited


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            visited = dfs(graph, label, visited)
            visited.pop(-1)
    return visited


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

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

G = {}
for m in range(M):
    k, v = list(map(int, input().split()))
    G.setdefault(k, []).append(v)
    G.setdefault(v, []).append(k)

count = 0
visited = []
visited.append(1)


def dfs(graph, start, visited=[]):
    global count
    if len(visited) == M:
        count += 1
    # visited.append(start)
    for label in graph.get(start, []):
        if label not in visited:
            visited.append(label)
            print(visited)
            visited = dfs(graph, label, visited)
            visited.pop(-1)
    return visited


dfs(G, 1, visited)
print(count)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
route = [[0 for i in range(N)] for l in range(N)]
count = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    route[a-1][b-1] = 1
    route[b-1][a-1] = 1

queue = [[[0],i] for  i in range(N) if route[0][i]]

while len(queue):
    r = queue.pop(0)
    n = r[1]
    r[0].append(n)
    if len(r[0]) == N:
        count += 1
    else:
        for i in range(N):
            if route[n][i] and i not in r[0]:
                r[1] = i
                queue.append(r)

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
r = [[] * N for i in range(N)]
reached = [0] * N
count = 0

def dfs(now, pre):
    global count
    if all(reached):
        count += 1
    for next in r[now]:
        if next != pre:
            if reached[next] == 0:
                reached[next] = 1
                dfs(next, now)
                reached[next] = 0
                
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    r[a].append(b)
    r[b].append(a)

dfs(0, -1)

print(count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

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

cnt = 0
for a in permutations(range(n)):
	print(a)
	if a[0] != 0:
		break
	tmp = 1
	for i in range(n-1):
		tmp = tmp * D[a[i]][a[i+1]]
	cnt += tmp
print(cnt)

Submission status: Wrong Answer

Solution code:
#ABC 054 C - One-stroke Path
N,M = map(int,input().split())
a = [0]*M
b = [0]*M
for m in range(M):
    a[m],b[m] = map(int,input().split())

ans = 0

for i in range(1<<M):
    cntlist = [0]*(N+1)
    for j in range(M):
        if ((i >> j) & 1) == 1:
            cntlist[a[j]] += 1
            cntlist[b[j]] += 1
    cnt = 0
    #print(cntlist)
    for n in range(2,N+1):
        if cntlist[1] != 1:
            break
        if cntlist[n] > 2 or cntlist[n] == 0:
            break
        if cntlist[n] == 1:
            if cnt == 1:
                break
            cnt += 1
        if n == N:
            #print(cntlist)
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
for j in ab:
    if j[::-1] not in ab:
        ab.append(j[::-1])
#print(ab)
ans = 0

#idx = [_ for _ in ab if _[0] == 1]
#idx = (ab.index(idx), 0)

searched = [0] * N
searched[0] = 1
length = 0

def dfs(n):
    
    global ans, length
    if length > N:
        return
    if sum(searched) == N:
        ans += 1
        return
    idx = [_ for _ in ab if _[0] == n]
    for idx in idx:
        id1, _ = (ab.index(idx), 0)
        next = ab[id1][1]
        searched[next - 1] = 1
        length += 1
    
        dfs(next)

dfs(1)
print(ans)
#print(searched)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
for j in ab:
    if j[::-1] not in ab:
        ab.append(j[::-1])

ans = 0

#idx = [_ for _ in ab if _[0] == 1]
#idx = (ab.index(idx), 0)

searched = [0] * N
searched[0] = 1
length = 0

def dfs(n):
    
    global ans, length
    if length > N - 1:
        return
    if sum(searched) == N:
        ans += 1
        return
    idx = [_ for _ in ab if _[0] == n]
    for idx in idx:
        id1, _ = (ab.index(idx), 0)
        next = ab[id1][1]
        searched[next - 1] = 1
        length += 1
    
        dfs(next)

dfs(1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

ans = 0

#idx = [_ for _ in ab if _[0] == 1]
#idx = (ab.index(idx), 0)

searched = [0] * N
searched[0] = 1

def dfs(n):
    global ans
    if sum(searched) == N:
        ans += 1
        return
    idx = [_ for _ in ab if _[0] == n]
    for idx in idx:
        id1, _ = (ab.index(idx), 0)
        next = ab[id1][1]
        searched[next - 1] = 1
    
        dfs(next)

dfs(1)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import permutations
import copy

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

adj = np.zeros((n,n))

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

cnt = 0
for p in permutations(range(n)):
	if p[0]!=1:
		continue
	tmp_adj = copy.deepcopy(adj)
	for i in range(n-1):
		if tmp_adj[p[i],p[i+1]] == 1:
			tmp_adj[p[i],p[i+1]] = 0
		else:
			break
	else:
		cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)
edges = []

# 無向グラフの表現
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    edges.append((a, b))

ans = 0

def dfs(graph, node_start, visited):
    global ans
    print(visited)
    if len(set(visited)) == len(set(graph)):
        ans += 1
        return
    for node_end in graph[node_start]:
        # 一回も訪れていない
        if node_end not in visited:
            dfs(graph, node_end, visited + [node_end])
    return

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

Submission status: Wrong Answer

Solution code:
from collections import *
n,m=map(int,input().split())

d=defaultdict(list)

for s in m*[0]:
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)

print(d)

#dはdefaultdict!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

def DFS_dict(point,TFlist):
#    print(TFlist)
#    print(d[point])
    if not False in TFlist:
        return 1
    ans=0
    for i in d[point]:
        if TFlist[i-1]:
            continue  #探索済みなら処理せず
        TFlist[i-1]=True #探索したのでTFlistをTrue
        ans+=DFS_dict(i,TFlist)
        TFlist[i-1]=False
    return ans

TFlist=[True]+[False]*(n-1)
print(DFS_dict(1,TFlist))

Submission status: Wrong Answer

Solution code:
import collections as c
n,m=map(int,input().split())
d=c.defaultdict(list)
for s in range(m):
  a,b=map(int,input().split())
  d[a].append(b)
#print(d)
ans=0
movecount=0
def search(defaultdict,list):
  global movecount
  global ans
  movecount+=1
  if list==[]:
    if movecount==m:
      ans+=1
      movecount-=1
    else:
      movecount-=1
  for item in list:
 #   print(item,"i")
 #   print(movecount)
    search(defaultdict,defaultdict[item])
  return ans
print(search(d,d[1]))

Submission status: Wrong Answer

Solution code:
import collections as c
n,m=map(int,input().split())
d=c.defaultdict(list)
for s in range(m):
  a,b=map(int,input().split())
  d[a].append(b)
print(d)
ans=0
movecount=0
def search(defaultdict,list):
  global movecount
  global ans
  movecount+=1
  if list==[]:
    if movecount==m:
      ans+=1
      movecount-=1
    else:
      movecount-=1
  for item in list:
 #   print(item,"i")
 #   print(movecount)
    search(defaultdict,defaultdict[item])
  return ans
print(search(d,d[1]))

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
ans = 0
if M >= N - 1:
    for i in list(itertools.combinations(ab, N - 1)):
        g = [0] * N
        for j in i:
            g[j[0] - 1] += 1
            g[j[1] - 1] += 1
        if g[0] == 1:
            f = 1
            for j in range(1, N):
                if g[j] > 2:
                    f = 0
                    break
        else:
            f = 0
        ans += f
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append(list(map(int, input().split())))
ans = 0
for i in list(itertools.combinations(ab, N - 1)):
    g = [0] * N
    for j in i:
        g[j[0] - 1] += 1
        g[j[1] - 1] += 1
    if g[0] == 1:
        f = 1
        for j in range(1, N):
            if g[j] > 2:
                f = 0
                break
    else:
        f = 0
    ans += f
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc054/tasks/abc054_c
import itertools


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

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

seq = [i + 1 for i in range(1, N)]
# print(list(itertools.permutations(seq)))

count = 0
for l in itertools.permutations(seq):
    # print(l)
    connected = True
    for i in range(len(l) - 1):
        a = min(l[i], l[i+1])
        b = max(l[i], l[i+1])
        if i == 0 and [1, a] not in C:
            connected = False
            break
        if [a, b] not in C:
            connected = False
            break
    if connected:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b = map(int, input().split())
    edge.append(set((a, b)))

p = list(map(lambda x: [1] + list(x), permutations([i for i in range(2, N + 1)])))

ans = 0

for root in p:
    for i in range(len(root) - 1):
        if not set((root[i], root[i + 1])) in edge:
            break
    else:
        print(root)
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            # v がSに含まれていないときはパス
            if (S & (1 << v)) == 0:
                continue

            #sub = S - {v}
            sub = S ^ (1 << v)

            for u in range(N):
                # sub に uが含まれていて、かつ uとvがへんで結ばれている
                if (sub & (1 << u)) and (Adj[u][v]):
                    dp[S][v] += dp[sub][u]
        ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
        return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def bit_dp(N, Adj):
    dp = [[0]*N for i in range(1 << N)]
    #dp[{0},0] = 1

    dp[1][0] = 1

    for S in range(1 << N):
        for v in range(N):
            # v がSに含まれていないときはパス
            if (S & (1 << v)) == 0:
                continue

            #sub = S - {v}
            sub = S ^ (1 << v)

            for u in range(N):
                # sub に uが含まれていて、かつ uとvがへんで結ばれている
                if (sub & (1 << u)) and Adj[u][v]:
                    dp[S][v] += dp[sub][u]
        ans = sum(dp[(1 << N) - 1][u] for u in range(1, N))
        return ans


def main():
    N, M = map(int, input().split())
    Adj = [[False]*N for _ in range(N)]

    for _ in range(M):
        a, b = map(int, input().split())
        Adj[a-1][b-1] = True
        Adj[b-1][a-1] = True
    ans = bit_dp(N, Adj)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[]for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    s[a-1].append(b-1)
    s[b-1].append(a-1)
c=0
k=[]
p=[[0,i]for i in s[0]]
for i in range(m-1):
    k=[]
    for j in range(len(p[:])):
        for h in range(len(s[p[j][-1]])):
            t=s[p[j][-1]]
            if not t[h] in p[j]:
                k.append(p[j]+[t[h]])
                if len(k[-1])==n:
                    c+=1
                    k.pop(-1)
    else:
        p=k[:]
print(c)

Submission status: Wrong Answer

Solution code:
import collections

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

root = 0
while len(stack) > 0:
    if False not in visited:
        root += 1
    pos = stack.pop()
    visited[pos] = True
    nexts = graph[pos]
    for i in range(n):
        if nexts[i] == False:
            continue
        if visited[i] == True:
            continue
        stack.append(i)

print(root)

Submission status: Wrong Answer

Solution code:
def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

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

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

Submission status: Wrong Answer

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