호반우가 학교에 지각한 이유 4

사실 호반우가 이세계에 도착한 순간부터 그의 이세계 모험은 생방송 플랫폼 트위치를 통해 지구에서 방송되고 있었다.

지금 방송 화면에는 호반우가 킹 슬라임 $N$마리가 있는 던전을 탐험하려는 모습이 나오고 있다. 모든 킹 슬라임은 서로 다른 슬라임 그룹에 속해 있고, 번호는 $1$번부터 $N$번까지 붙어 있다.

방송의 유일한 시청자인 상호는 TWIP의 슬롯머신을 $M$번 돌려, 호반우가 던전을 탐험하기 전에 슬라임 그룹들을 합치려 한다.

슬롯머신을 돌리면 $1 \le a < b \le N$을 만족하는 양의 정수 쌍 $a, b$가 적힌 아이템이 나온다. 이 아이템은 인벤토리에 저장해 두었다가 슬라임 그룹을 합치는 데 사용할 수 있다.

인벤토리에서 $a, b$가 적힌 아이템을 소비하면 $a$번 킹 슬라임이 속한 그룹과 $b$번 킹 슬라임이 속한 그룹을 합칠 수 있다. 다만 두 킹 슬라임이 이미 같은 그룹에 속해 있다면 합쳐지지 않는다. 두 그룹이 합쳐지면 합쳐진 그룹의 킹 슬라임 마릿수에서 1을 뺀 만큼의 미니 슬라임이 만들어진다.

상호는 슬롯머신을 돌린 횟수에 따라 던전에 슬라임(킹 슬라임과 미니 슬라임)을 최대 몇 마리까지 만들 수 있을지 궁금해졌다. 스트리머로서 유일한 시청자인 상호에게 답을 알려 주자.

첫 번째 줄에 슬라임의 수 $N$과 슬롯머신을 돌린 횟수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 300\,000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 슬롯머신에서 나온 아이템에 적힌 양의 정수 쌍 $a, b$가 공백으로 구분되어 순서대로 주어진다. ($1 \le a < b \le N$)

$M$개의 줄에 답을 한 줄씩 출력한다. $i$번째 줄에는 슬롯머신을 1번부터 $i$번까지 돌려 얻은 아이템을 모두 사용했을 때, 던전에 있을 수 있는 슬라임 마릿수의 최댓값을 출력한다.

입출력의 양이 많으므로 빠른 입출력을 사용하는 것을 권장합니다. 언어별 빠른 입출력 방법은 아래를 참고해 주세요.

• C++: cin과 cout을 쓰는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄을 바꿀 때는 endl 대신 '\n'을 사용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.