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

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

현재 방송 화면에는 호반우가 $N$마리의 킹 슬라임이 있는 던전을 탐험하려는 모습이 송출되고 있다. 모든 킹 슬라임은 서로 다른 슬라임 그룹에 속해있으며, $1$번부터 $N$번까지 번호가 주어져 있다.

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

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

인벤토리에서 $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$번째 줄에는 슬롯머신을 $i$번까지 돌려서 얻은 아이템들을 사용했을 때 던전에 있을 수 있는 슬라임들의 마릿수 중 최댓값을 출력한다.

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고해 주세요.

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