물류 센터

어떤 공장에 제조 라인이 $n$개 있고, 보관실도 같은 수만큼 있다. 제조 라인의 물건을 대응하는 보관실로 곧장 나르는 컨베이어 레인도 같은 수만큼 나란히 놓여 있다. 이제 인접한 두 레인 사이 여러 지점에 로봇 팔을 설치한다. 로봇 팔은 한쪽 레인의 물건을 집어 다른 쪽 레인에 내려놓고, 반대 방향으로도 옮긴다. 그래서 서로 다른 제조 라인의 물건이 여러 보관실로 섞여 들어간다.

로봇 팔의 위치에 따라 각 제조 라인의 물건이 닿을 수 있는 보관실이 정해진다. 컨베이어 레인의 수와 로봇 팔의 위치가 주어질 때, 보관실마다 물건을 받을 수 있는 제조 라인의 수를 구하라.

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

n m
x1 y1
...
xm ym

첫 줄의 정수 $n$ ($2 \le n \le 200000$)은 컨베이어 레인의 수다. 레인에는 1번부터 $n$번까지 번호가 붙어 있고, 번호가 1만큼 차이 나는 두 레인은 인접하다. 모든 레인은 $x = 0$에서 시작해 $x = 100000$에서 끝난다. 다른 정수 $m$ ($1 \le m < 100000$)은 로봇 팔의 수다.

이어지는 $m$개의 줄에는 로봇 팔의 위치가 두 정수 $x_i$ ($0 < x_i < 100000$)와 $y_i$ ($1 \le y_i < n$)로 주어진다. $i$번째 로봇 팔은 $x = x_i$ 지점에서 $y_i$번 레인과 $y_i + 1$번 레인 중 한쪽의 물건을 집어 같은 $x$ 좌표의 다른 쪽 레인에 내려놓는다. 물건이 로봇 팔을 지날 때 그 팔로 레인을 바꿀지 그대로 지나갈지는 물건마다 자유롭게 정한다.

두 로봇 팔의 $x$ 좌표가 같은 경우는 없다. 즉 $i \ne j$이면 $x_i \ne x_j$이다.

위 그림은 첫 번째 예제 입력의 배치를 나타낸다.

한 줄에 $n$개의 정수를 공백으로 구분해 출력한다. $i$번째 정수는 $i$번 컨베이어 레인에 이어진 보관실이 물건을 받을 수 있는 제조 라인의 수다.