페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5414

Making Friends 1초 256MB

문제

**Note: the time limit for this problem is 3s, 50% larger than the default. The memory limit is twice the default.**

There are initially M (1≤M≤2⋅105) pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N.

The cows are leaving the farm for vacation one by one.

On day i, the i-th cow leaves the farm, and all pairs of the i-th cow's friends still present on the farm become friends. How many new friendships are formed in total?​


입력

The first line contains N and M.

The next M lines contain two integers ui and vi denoting that cows ui and vi are friends (1≤ui,vi≤N, ui≠vi). No unordered pair of cows appears more than once.​ 


출력

One line containing the total number of new friendships formed. Do not include pairs of cows that were already friends at the beginning. 


예제1

입력
7 6

1 3
1 4
7 1
2 3
2 4
3 5
출력
5


출처

USACO 2022 December Platinum

역링크 공식 문제집만