#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [💭] [💡] [🎈] */

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int n, m;
    cin >> n >> m;

    map<int, vector<int>> v;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].emplace_back(y);
    }

    vector<vector<int>> r;
    for (const auto &kv : v) r.emplace_back(kv.second);

    set<int> pos;
    pos.emplace(n);

    for (auto &x : r) {
        queue<int> erq, emq;
        for (auto &y : x) {
            if (pos.count(y)) {
                erq.emplace(y);
            }
            if (pos.count(y - 1) || pos.count(y + 1)) {
                emq.emplace(y);
            } 
        }
        while (erq.size()) pos.erase(erq.front()), erq.pop();
        while (emq.size()) pos.emplace(emq.front()), emq.pop();
    }

    cout << pos.size() << endl;

    return 0;
}
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

std::vector<std::vector<int> > hen;
std::vector<int> dist;
std::vector<int> stack;
std::vector<int> stack_res;
void dfs0(int i, int prev, int goal = -1) {
	stack.push_back(i);
	if (i == goal) stack_res = stack;
	for (auto j : hen[i]) if (j != prev) {
		dist[j] = dist[i] + 1;
		dfs0(j, i, goal);
	}
	stack.pop_back();
}

int cnt = 0;
std::vector<int> res;
std::vector<int> avoid;

void dfs1(int i, int prev) {
	res[i] = cnt;
	for (auto j : hen[i]) if (j != prev) {
		if (avoid[i] == j) continue;
		cnt++;
		dfs1(j, i);
		cnt++;
	}
	for (auto j : hen[i]) if (j != prev) {
		if (avoid[i] != j) continue;
		cnt++;
		dfs1(j, i);
		cnt++;
	}
}

int main() {
	int n = ri();
	hen.resize(n);
	for (int i = 1; i < n; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	dist.assign(n, 0);
	dfs0(0, -1);
	int t0 = std::max_element(dist.begin(), dist.end()) - dist.begin();
	dist.assign(n, 0);
	dfs0(t0, -1);
	int t1 = std::max_element(dist.begin(), dist.end()) - dist.begin();
	
	dist.assign(n, 0);
	
	dfs0(t0, -1, t1);
	
	auto tmp = stack_res;
	avoid.resize(n, -1);
	for (int i = 0; i + 1 < (int) tmp.size(); i++) avoid[tmp[i]] = tmp[i + 1];
	
	/*
	for (auto i : tmp) std::cerr << i << std::endl;
	*/
	res.resize(n);
	dfs1(tmp[0], -1);
	
	for (int i = 0; i < n; i++) {
		if (i) printf(" ");
		printf("%d", res[i] + 1);
	}
	puts("");
	
	return 0;
}
