문제
아래 그림은 어느 한 스키장의 7개의 휴식 지점들과 휴식지점들 사이에 스키를 타고 내려갈 수 있는 길을 나타내고 있다. 지점 에서 출발하여 지점 에 도착할 수 있는 방법은 모두 13가지다. 예를 들면, 1에서 2를 거쳐 7까지 가는 방법 1→2→7이 있고, 또 1→2→6→7 등이 있다.
스키장의 각 지점들 사이에 내려갈 수 있는 길이 주어지면 출발지점에서 도착점까지 내려가는 방법을 모두 찾는 프로그램을 작성하시오. 출발지점은 1지점이고 도착지는 마지막지점이며, 지점의 작은 번호가 큰 번호보다 더 높은 곳에 위치한다.
입력
첫줄에 휴식지점의 개수 N(5≤N≤1000)과 내려갈 수 있는 길의 개수 M(5≤M≤499500))이 공백으로 구분하여 주어진다. 그 다음 줄부터 M개의 줄에 각 지점들 사이에 내려갈 수 있는 경로가 주어진다.
출력
한 줄에 시작점에서 도착점까지 내려가는 총 가짓수를 출력한다.
예제
7 16
1 2
1 3
1 4
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 5
3 7
4 6
4 7
5 7
6 7
13
출처
2012 지역예선 초등부 문제 변환
로그인해야 코드를 작성할 수 있어요.