Making Friends

면접 대비

시간 제한3초메모리 제한1024 MB

요약

소들이 하루에 한 마리씩 떠나고, 떠날 때 남아 있는 친구들끼리 모두 친구가 된다. 새로 생기는 친구 관계의 총 개수를 센다.

난이도: 보통10점 중 7점
유형: 그래프, 유니온 파인드, 구현, 수학
정답자: 아직 제출이 없습니다

문제

There are initially $M$ ( $1\le M\le 2\cdot 10^5$ ) pairs of friends among FJ's $N$ ( $2\le N\le 2\cdot 10^5$ ) cows labeled $1\dots 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 $u\_i$ and $v\_i$ denoting that cows $u\_i$ and $v\_i$ are friends ( $1\le u\_i,v\_i\le N$ , $u\_i\neq v\_i$ ). 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.

힌트

On day $1$ , three new friendships are formed: $(3,4)$ , $(3,7)$ , and $(4,7)$ .

On day $3$ , two new friendships are formed: $(4,5)$ and $(5,7)$ .

예제1

예제 1
입력
```
7 6
1 3
1 4
7 1
2 3
2 4
3 5
```
예상 출력
```
5
```