Pythonの深さ優先探索で失敗した話

ハミルトン閉路が存在するか判定する問題。入力は、
n m
x_1 y_1
x_2 y_2
... ...
x_m y_m
で与えられる。（nは頂点数、mは辺の数。x_i,y_iは頂点x_iとy_iを結ぶ辺が存在することを表す）

#合ってるコード(しかしこれもn=15くらいだと落ちるね......)
n,m = map(int,input().split())
edge = []
for i in range(n):
    T = [0]*n
    edge.append(T)
for i in range(m):
    x,y = map(int,input().split())
    edge[x][y] = 1
    edge[y][x] = 1

def dfs(cur, checked, rest): #curは現在いる点、checkedは訪れた点、restはこれから訪れる点
    if len(rest) == 0:
        if edge[cur][0] == 1: #全点探索が終了したら、現在いる点と点0の間に辺があるかどうかを判定
            print('Yes')
            exit()
    else:
        for i in range(n):
            if edge[cur][i] == 1:
                if (i in rest) and (i not in checked):
                    L = []
                    for j in range(len(rest)):
                        if rest[j] != i:
                            L.append(rest[j])
                    temp = [i]
                    for j in range(len(checked)):
                        temp.append(checked[j]) #ここcopyに注意
                    dfs(i, temp, L)

P = [i for i in range(1, n)] #これから訪れる頂点のリスト
dfs(0, [], P) #点0からスタート
print('No')

間違えた理由はいくつかあって、まず
・dfsを同じ深さのfor文でやると、前の処理がそのまま後ろのfor文に引き継がれる（同時並行で進むわけではない）
・pythonの　= は参照渡し（なので値だけコピーしたいならdeepcopyを使わないといけないけど、deepcopyはバカ遅い）

#間違っているコード
n,m = map(int,input().split())
edge = []
for i in range(m):
    s,e = map(int,input().split())
    edge.append([s,e])

def dfs(cur, checked, rest):
    if len(rest) == 1:
        flag = False
        for i in range(len(edge)):
            if edge[i][0] == 0:
                if edge[i][1] == rest[0]:
                    flag = True
                    break
            elif edge[i][1] == 0:
                if edge[i][0] == rest[0]:
                    flag = True
                    break
        if flag:
            return True
        else:
            return False
    else:
        flag = False
        for i in range(len(edge)):
            temp = checked
            if edge[i][0] == cur:
                if edge[i][1] in rest:
                    if edge[i][1] not in checked:
                        flag = True
                        L = []
                        for j in range(len(rest)):
                            if rest[j] != edge[i][1]:
                                L.append(rest[j])
                        temp.append(edge[i][1])
                        return dfs(edge[i][1], temp, L)
            elif edge[i][1] == cur:
                if edge[i][0] in rest:
                    if edge[i][0] not in checked:
                        flag = True
                        L = []
                        for j in range(len(rest)):
                            if rest[j] != edge[i][0]:
                                L.append(rest[j])
                        temp.append(edge[i][0])
                        return dfs(edge[i][0], temp, L)
        if not flag:
            return False

P = [i for i in range(1, n)]
if dfs(0, [], P):
    print('Yes')
else:
    print('No')