9050: 방향 그래프 경로 탐색2
[만든사람 : ]
문제 설명
방향그래프의 1번 정점에서 N번 정점까지 가는 모든 경로의 경우를 출력하는 프로그램을 작성하시오. 아래 그래프 1번 정점에서 5번 정점으로 가는 가지 수는 아래와 같이 총 6가지이다.
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
입력 설명
첫 줄에 정점의 수 N(1<=N<=20)와 간선의 수 M이 공백으로 구분되어 입력된다.
두번 째 줄에 M줄에 걸쳐 간선의 정보가 주어진다.
두번 째 줄에 M줄에 걸쳐 간선의 정보가 주어진다.
출력 설명
1번 정점에서 N번 정점까지 가는 모든 경로의 총 가지수 만큼 각 줄에 그 경로를 출력한다.
입력 예시 Copy
5 9
1 2
2 1
1 3
1 4
2 3
3 4
2 5
4 2
4 5
출력 예시 Copy
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5