스폰지밥의 책 컬렉션

스폰지밥은 해저 역사에 관한 책 $2n$권으로 이루어진 컬렉션을 샀다. 각 책에는 고유한 번호가 있다. 번호 1부터 $n$까지의 책은 초기 해저 역사를 담고 있고, 번호 $n+1$부터 $2n$까지의 책은 새로운 역사를 다룬다. 스폰지밥은 책을 번호 오름차순으로 선반 하나에 꽂았다.

스폰지밥이 출근한 사이 애완 달팽이 개리가 책을 옮기기 시작했다. 개리는 한 번에 책 두 권을 골라, 첫 번째 책을 두 번째 책이 있던 자리에, 두 번째 책을 첫 번째 책이 있던 자리에 놓는다. 두 책의 위치만 서로 바뀐다.

집에 돌아온 스폰지밥은 장난을 알아채고 몹시 화가 났다. 다행히 방에 설치된 카메라가 개리의 모든 행동을 기록했다. 스폰지밥은 초기 역사 책을 특히 아끼기 때문에, 카메라 기록을 보고 교환할 때마다 선반의 처음 $n$개 위치에 번호 1부터 $n$ 사이의 책이 몇 권 있는지 알고 싶어 한다. 더 정확히 말하면, 교환이 끝날 때마다 $1 \le x \le n$을 만족하고 번호 $x$인 책이 처음 $n$개 위치 중 하나에 있는 $x$의 개수를 구한다.

개리가 교환한 기록이 주어지면, 각 교환 후 위치 1부터 $n$까지에 있는 초기 역사 책의 수를 계산하는 프로그램을 작성하라.

첫 줄에 정수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 이는 초기 역사 책의 수이자 새 역사 책의 수와 같다.

둘째 줄에 정수 $m$ ($1 \le m \le 100\,000$)이 주어진다. 개리가 한 교환의 횟수이다.

이어지는 $m$개 줄에는 각각 정수 $i_k$, $j_k$ ($1 \le i_k, j_k \le 2n$)가 주어진다. 이는 $k$번째 교환에서 위치 $i_k$와 $j_k$에 있던 책을 서로 맞바꿨다는 뜻이다.

한 줄에 $m$개의 수를 출력한다. $k$번째 수는 $k$번째 교환 후 위치 1부터 $n$까지에 있는 초기 역사 책의 수이다.