경로탐색

def DFS(v):
    global cnt
    if v == n:
        cnt += 1
        for k in path:
            print(k, end= ' ')
        print()
    else:
        for i in range(1,n+1):
            if ch[i] == 0 and g[v][i] == 1:
                ch[i] = 1
                path.append(i)
                DFS(i)
                ch[i] = 0
                path.pop()

if __name__ == "__main__":
    n, m = map(int,input().split())
    # 1 부터 n 까지 연결 여부, 방문 여부를 위한 배열 g 와 ch
    g = [[0] * (n + 1) for _ in range(n + 1)]
    ch = [0] * (n + 1)
    # 항상 1부터 방문시작을 하므로 1로 체크한다.
    ch[1] = 1 
    cnt = 0
    path = []
    path.append(1)
    for _ in range(m):
        a, b = map(int,input().split())
        g[a][b] = 1
    DFS(1)
    print(cnt)


# 노드가 n개이고, m개의 간선이 주어진다. 방향성이 있는 그래프에서 1부터 n까지 갈 수 있는 모든 경로의 수를 구하자
# 그 경로도 구해보자.

# 문제를 푸려면 역시 트리 구조를 그려보는 것이 좋다.DFS로 문제를 풀 것이고, 항상 1로 시작해서 1과 연결된 노드
# 를 확인하고 연결된 노드 순서대로 DFS 재귀 호출을 한다. 중요한 것은 방문한 노드 i 가 재귀 호출의 인자로 넘어간다.
# 왜냐하면 방문한 노드 i와 연결된 노드로 넘어가서 다시 경로를 추가하기 때문!!

# 1. 인접행렬을 만든다.
# 2. 이미 방문한 노드를 다시 방문하지 않기 위해 ch 배열을 만든다.
# 3. 다음 경로를 결정할 때, 이미 방문하지 않았고 현재 방문하고 있는 노드와 인접한 노드인 것을 확인
# 4. 재귀호출 시 해당 방문할 노드를 매개변수로 넘긴다. 또한 방문 표시를 위해 ch[i] = 1
# 5. 재귀호출을 하고 첫 번째 경로가 나오고 나면 다시 back을 하기 때문에 원래대로 되돌려야하고 
# 재귀호출 다음 줄에 ch[i] = 0라고 표시.
# 해당 경우의 경로를 출력하기 위해서 방문할 때 path.append(i) 다시 back을 위해 재귀호출 다음에 path.pop

# 처음 배웠던 것을 그대로 활용해서 트리구조를 그려보면 쉽게 풀 수 있을거다!