경로의 개수
매우 쉬움
유형
프로그래밍
배점
100점
참여자
123
정답률
87.8%
1
0
문제
구름이가 사는 구름 나라는 개의 섬으로 이루어져 있다. 각 섬은
번부터
번까지 번호가 매겨져 있다.
구름 나라의 정부에서는 사람들이 섬들 사이를 편하게 이동할 수 있도록 섬과 섬 사이에 많은 다리를 설치했다. 설치된 다리들은 아래 특징들을 만족한다.
번 섬에 설치된 모든 다리는
번 섬과 연결되어 있다. 단,
번 섬에 설치된 모든 다리는
번 섬과 연결되어 있다.
- 모든 다리는 단방향으로만 이동 가능하다. 따라서
번 섬을 제외하고는 번호가 감소하는 섬으로 이동할 수 없다. 마찬가지로
번 섬에서
번 섬으로도 이동할 수 없다.
구름 나라에 있는 섬의 개수와 각 섬에 연결된 다리의 개수가 주어졌을 때, 번 섬에서
개의 다리를 이용해 다시
번 섬으로 돌아올 수 있는 경로의 개수를 구하라.
입력
첫째 줄에 섬의 개수 이 주어진다.
둘째 줄에 이 공백을 두고 주어진다.
는
번 섬에 설치된 다리의 개수를 의미한다.
- 입력에서 주어지는 모든 수는 정수이다.
- 정답이
보다 작은 입력만 주어진다.
출력
번 섬에서 출발해서 다시
번 섬으로 돌아오는 경로의 개수를 출력한다.