4회 문제풀이 05 / ABC 204 C - Tour
ABC 204 C - Tour
【문제 개요】
AtCoder 나라에는 1부터 N까지의 번호가 붙은 N개의 도시와 1부터 M까지의 번호가 붙은 M개의 도로가 있습니다.
도로 i를 통과하면 도시 Aᵢ에서 Bᵢ에 이동하는 것이 가능합니다. 도시 Bᵢ에서 도시 Aᵢ로 통행은 불가능합니다.
퓨마는 어딘가의 도시에서 출발해서, 0개 이상의 도로를 사용하여 이동해, 어딘가의 도시를 목적지로 하는 여행을 계획하고 있습니다.
스타트 지점과 목적지 지점의 도시의 조합으로 할수있을만한 조합은 몇가지 입니까?
【전제】
- 2 ≦ N ≦ 2000
- 0 ≦ M ≦ min(2000, N(N-1))
- 1 ≦ Aᵢ, Bᵢ ≦ N
- Aᵢ ≠ Bᵢ
- (Aᵢ, Bᵢ)는 다르다.
- 입력의 모든 수치는 정수이다.
【입력 형태】
1
2
3
4
N M
A₁ B₁
...
Aₘ Bₘ
【출력 형태】
답변을 출력하시오.
【예시】
입력 예 1
1
2
3
4
3 3
1 2
2 3
3 2
출력 예 1
1
7
스타트 지점과 목적지 지점의 조합으로 생각 가능한것은 (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)의 7개이다.
입력 예 2
1
3 0
출력 예 2
1
3
스타트 지점과 목적지 지점의 조합으로 생각 가능한것은 (1, 1), (2, 2), (3, 3)의 3개이다.
입력 예 3
1
2
3
4
5
4 4
1 2
2 3
3 4
4 1
출력 예 3
1
16
스타트 지점과 목적지 지점으로 모든 도시의 조합이 가능합니다.
このポストは作成者の CC BY 4.0 ライセンスによって保護されます。