#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int main() {
	cin >> n >> m;
	vector<int> x(m), y(m); vector<pair<int, int> > st(m);
	for (int i = 0; i < m; i++) cin >> x[i] >> y[i], y[i]--, st[i] = make_pair(x[i], y[i]);
	sort(st.begin(), st.end());
	for (int i = 0; i < m; i++) x[i] = st[i].first, y[i] = st[i].second;
	vector<vector<int> > ps(n - 1);
	for (int i = 0; i < m; i++) ps[y[i]].push_back(i);
	vector<int> pl(m, -1), pr(m, -1);
	for (int i = 0; i < m; i++) {
		if (y[i] >= 1) {
			int ptr = lower_bound(ps[y[i] - 1].begin(), ps[y[i] - 1].end(), i) - ps[y[i] - 1].begin() - 1;
			if (ptr >= 0) pl[i] = ps[y[i] - 1][ptr];
		}
		if (y[i] <= n - 3) {
			int ptr = lower_bound(ps[y[i] + 1].begin(), ps[y[i] + 1].end(), i) - ps[y[i] + 1].begin() - 1;
			if (ptr >= 0) pr[i] = ps[y[i] + 1][ptr];
		}
	}
	vector<int> dpl(m), dpr(m);
	for (int i = 0; i < m; i++) {
		if (pl[i] != -1) dpl[i] = dpl[pl[i]] + 1;
		if (pr[i] != -1) dpr[i] = dpr[pr[i]] + 1;
	}
	for (int i = 0; i < n; i++) {
		if (i) cout << ' ';
		int ret = -1;
		if (i <= n - 2 && ps[i].size()) ret = dpl[ps[i].back()] + dpr[ps[i].back()];
		if (i >= 1 && ps[i - 1].size()) ret = max(ret, dpl[ps[i - 1].back()] + dpr[ps[i - 1].back()]);
		cout << ret + 2;
	}
	cout << endl;
	return 0;
}
### Prompt

Generate a cpp solution to the following problem:

Example

Input

4 3
1000 1
2000 2
3000 3


Output

2 3 4 4

### Response

```cpp
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int main() {
	cin >> n >> m;
	vector<int> x(m), y(m); vector<pair<int, int> > st(m);
	for (int i = 0; i < m; i++) cin >> x[i] >> y[i], y[i]--, st[i] = make_pair(x[i], y[i]);
	sort(st.begin(), st.end());
	for (int i = 0; i < m; i++) x[i] = st[i].first, y[i] = st[i].second;
	vector<vector<int> > ps(n - 1);
	for (int i = 0; i < m; i++) ps[y[i]].push_back(i);
	vector<int> pl(m, -1), pr(m, -1);
	for (int i = 0; i < m; i++) {
		if (y[i] >= 1) {
			int ptr = lower_bound(ps[y[i] - 1].begin(), ps[y[i] - 1].end(), i) - ps[y[i] - 1].begin() - 1;
			if (ptr >= 0) pl[i] = ps[y[i] - 1][ptr];
		}
		if (y[i] <= n - 3) {
			int ptr = lower_bound(ps[y[i] + 1].begin(), ps[y[i] + 1].end(), i) - ps[y[i] + 1].begin() - 1;
			if (ptr >= 0) pr[i] = ps[y[i] + 1][ptr];
		}
	}
	vector<int> dpl(m), dpr(m);
	for (int i = 0; i < m; i++) {
		if (pl[i] != -1) dpl[i] = dpl[pl[i]] + 1;
		if (pr[i] != -1) dpr[i] = dpr[pr[i]] + 1;
	}
	for (int i = 0; i < n; i++) {
		if (i) cout << ' ';
		int ret = -1;
		if (i <= n - 2 && ps[i].size()) ret = dpl[ps[i].back()] + dpr[ps[i].back()];
		if (i >= 1 && ps[i - 1].size()) ret = max(ret, dpl[ps[i - 1].back()] + dpr[ps[i - 1].back()]);
		cout << ret + 2;
	}
	cout << endl;
	return 0;
}
```