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

현재 방송 화면으로 호반우가 $1$번부터 $N$번까지 크기가 1인 $N$마리의 슬라임이 매일 리젠되는 던전을 탐험하려는 모습을 볼 수 있다.

방송의 유일한 시청자인 상호는 "트윕"의 슬롯머신을 $M$일 동안 매일 한 번씩 사용해 호반우가 오기 전에 슬라임들을 합치려고 한다.

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

양의 정수 쌍 $a, b$를 사용하면 $a$번 슬라임이 속한 슬라임과 $b$번 슬라임이 속한 슬라임이 합쳐진다. 이때 이미 $a$번 슬라임과 $b$번 슬라임이 같은 슬라임에 속해있다면 합쳐지지 않는다.

합쳐진 슬라임의 크기는 $($합쳐질 두 슬라임의 크기$)+(N$마리의 슬라임 중 합쳐진 슬라임에 속한 슬라임의 마릿수$)$ 이다.

상호는 매일 던전에 있는 슬라임들의 크기의 합을 얼마나 크게 할 수 있을지 궁금해졌다. 스트리머로서 유일한 시청자인 상호에게 답을 알려주자!

Input

첫 번째 줄에 슬라임의 수 $N$과 상호가 슬롯머신을 돌린 일수인 $M$이 공백을 두고 주어진다. $(2 \le N \le 200\,000, 1 \le M \le 300\,000)$

두 번째 줄부터 $M$개의 줄에 걸쳐 상호가 매일 슬롯머신을 돌려 나온 양의 정수 쌍 $a, b$가 순서대로 공백을 두고 주어진다. $(1 \le a < b \le N)$

Output

$M$개의 줄에 걸쳐 답을 출력한다.

$i$번째 줄에는 슬롯머신을 $i$번째 돌린 날에 던전에 있을 수 있는 슬라임들의 크기의 합의 최댓값을 출력한다.

Examples

Input 1

2 1
1 2

Output 1

3

Input 2

2 2
1 2
1 2

Output 2

3
3