#include <cstdio>
#include <cstring>

int lst[1000005], a[1000005], b[1000005], choice[1000005], lst2[1000005], ans[1000005];
bool mark[1000005], bchosen[1000005];

int main() {
	int n, m, N = 0, lst1 = 0; scanf("%d%d", &n, &m), N = n;
	for (int i = 1; i <= n; ++ i) scanf("%d%d", a + i, b + i);
	for (int i = 1; i <= n; ++ i) {
		bchosen[i] = mark[b[i]];
		if (!mark[a[i]]) choice[i] = 0, mark[a[i]] = true;
		else if (!mark[b[i]]) choice[i] = 1, mark[b[i]] = true;
		else {N = i - 1; break;}
	}
	for (int i = N; i; -- i)
		if (choice[i] == 0) lst[a[i]] = ((lst[b[i]] && !bchosen[i]) ? lst[b[i]] : i);
		else lst[b[i]] = i;
	if (N == n) {
		lst1 = 0; while (lst1 < n && choice[lst1 + 1] == 0) ++ lst1;
		while (lst2[0] < lst1 && !mark[b[lst2[0] + 1]]) mark[b[++ lst2[0]]] = true;
		if (lst2[0] == n) lst2[0] = 1;
		else ++ lst2[0];
		for (int i = 1; i <= m; ++ i) lst2[i] = lst2[0];
		for (int i = lst2[0] == 1 ? n : lst2[0] - 1; i; -- i) lst2[b[i]] = i;
	}
	if(n>=10000&&N==n)return -1;
	for (int i = 1; i <= m; ++ i) {
		int x = lst[i];
		if (x && (choice[x] == 1 || (choice[x] == 0 && bchosen[x]))) ++ ans[x];
		else if (x && choice[x] == 0 && !bchosen[x]) ++ ans[N == n ? lst2[b[x]] : N + 1];
		else if (N != n) ++ ans[N + 1];
		else ++ ans[lst2[i]];
	}
	for (int i = 1; i <= n; ++ i) printf("%d\n", ans[i]);
	return 0;
}