문제
FJ의 N(2≤N≤2⋅10 5 )마리 소들 사이에는 처음에 1…N으로 표시된 M(1≤M≤2⋅10 5 )쌍의 친구가 있습니다.
소들이 하나둘씩 휴가를 위해 농장을 떠난다.
i일째 되는 날, i번째 소가 농장을 떠나고, i번째 소의 친구 중 농장에 남아 있는 모든 쌍이 친구가 됩니다. 총 몇 쌍의 새로운 우정이 형성될까요?
입력
첫째 줄에 N과 M이 주어진다.
다음 M개의 줄에는 두 개의 정수 ui와 vi가 주어지는데, 이는 소 ui와 vi가 친구임을 나타냅니다(1≤ui,vi≤N, ui≠vi). 순서 없는 소 쌍은 한 번만 나타납니다.
출력
새로 형성된 친구의 총 수를 한 줄에 표시합니다. 처음에 이미 친구였던 소 쌍은 포함하지 마세요.
예제
7 6
1 3
1 4
7 1
2 3
2 4
3 5
5
힌트
태그
출처
USACO 2022 December Platinum
로그인해야 코드를 작성할 수 있어요.