파일 업로드

농장 통로

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

농부인 준석이와 규민이는 각자가 가진 수많은 농장들을 하나로 연결하는 통로를 만들고자 합니다. 각각의 N개의 농장(1 <= N <= 100,000)에서 하나의 농장에서 다른 농장으로 하나씩 향하는 통로를 만들도록 약속했습니다. 

즉, 총 N개의 통로를 만들게 됩니다. 준석이와 규민이는 각자 고용한 농부들에게 해당 작업을 지시했으나, 시간이 흘러 실제로 만들어진 통로는 M개(1 <= M < N)에 불과했습니다.

누구의 잘못인지를 파악하기 위해 준석이와 규민이는 개발자에게 문제를 의뢰합니다.

개발자인 당신은, 현재까지 만들어진 M개의 통로가 얼마나 많은 방법으로 만들어질 수 있는지 계산하고자 합니다. 예를 들어, 농장 3과 농장 4를 연결하는 통로가 이미 만들어져 있다면, 농장 3이 해당 통로를 만든 가능성과 농장 4가 길을 만든 가능성이 있습니다. 

M개의 통로를 만들 수 있는 경우의 수를 계산하여 준석이와 규민이를 의뢰를 해결해주세요.  이 때 결과를 1,000,000,007로 나머지 연산한 값을 출력해야 합니다.

💻 입력
  • 줄 1: 두 개의 공백으로 구분된 정수 N과 M
  • 줄 2..1+M: 줄 i+1은 i번째 통로에 대해 설명합니다. 각 줄은 두 개의 공백으로 구분된 정수 u_i와 v_i (1 <= u_i, v_i <= N, u_i != v_i)로 표시된 각자의 농장을 통로로 연결합니다.
🖨️ 출력
  • 줄 1: M개의 통로를 만들 수 있는 경우의 수를 1,000,000,007로 나눈 나머지입니다. 위의 조건을 만족하는 할당이 없다면 0을 출력합니다.

💻 예제 입력 1
5 4
1 2
3 2
4 5
4 5
🖨️ 예제 출력 1
6

출처: USACO 2012 January Contest, Gold Division Problem 3. Bovine Alliance