Как найти цикл в графе

def DFS(G, s): 
    n = len(G)
    used = [False] * n+1
    S = []
    S.append(s)
    used[s] = True
    b = [s]
    
 
    while(S != []): 
        v = S[-1] 
        S.pop()
        g = s
        for i in G[v]:
            if (used[i] == False): 
                S.append(i)
                b.append(i)
                used[i] = True
        if s == g:
            if len(G[v]) == 1:
                continue
            else:
                for i in G[v]:
                    if (used[i] == True):
                        b.append(i)
                        return(b[v-1:i+1])
 
graph = {1: set([2]),
         2: set([3, 4]),
         3: set([2, 4]),
         4: set([2, 3, 5]),
         5: set([4])}
k = 1
print(DFS(graph, k))

used = [False] * (n+1)

# Ввод графа (списком ребер)
 
def get_graph():
    (n,m)=map(int,input().split())
    graph=[]
    for _ in range(m):
        (a,b)=map(int,input().split())
        graph.append((a,b))
    return graph    
 
# Обход в глубину, совмещенный с поиском фундаментальных циклов
 
def dfs_loops(graph):
    
    stack=[1]
    chk=[1]
    
    while True:
    
        if len(stack)==0:
            print("OK")
            return
        
        v=stack[-1]
        
        for (a,b) in graph:
            
            #if (a==v) and not (b in chk):  # это для ориентированного графа
 
            if (a == v) and not (b in chk) or \
               (b == v) and not (a in chk):
                
                if a==v:
                    bb=b
                else:
                    bb=a
                   
                stack.append(bb)
                chk.append(bb)
                
                # Проверка цикла
                
                sz=len(stack)
                
                for i in range(sz-2):
 
                    #if (bb,stack[i]) in graph:  # это для ориентированного графа
 
                    if (bb,stack[i]) in graph or (stack[i],bb) in graph: 
                        print("Loop:",end=' ')
                        for j in range(i,sz):
                            print(stack[j],end=' ')
                        print()
                break
        
        else:
            stack.pop()
 
g=get_graph()
 
dfs_loops(g)