class UnionFind: def __init__(self,n): self.n = n self.parent_size = [-1]*n def leader(self,a): if self.parent_size[a] < 0: return a self.parent_size[a] = self.leader(self.parent_size[a]) return self.parent_size[a] def merge(self,a,b): x, y = self.leader(a), self.leader(b) if x == y: return if abs(self.parent_size[x]) < abs(self.parent_size[y]): x, y = y, x self.parent_size[x] += self.parent_size[y] self.parent_size[y] = x return def same(self,a,b): return self.leader(a) == self.leader(b) def size(self,a): return abs(self.parent_size[self.leader(a)]) def groups(self): result = [[] for _ in range(self.n)] for i in range(self.n): result[self.leader(i)].append(i) return [r for r in result if r != []] N, Q = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(Q)] L = [] for A, B in AB: L.append(A) L.append(B) S = sorted(set(L)) idx = dict() idxR = dict() for i in range(len(S)): idx[S[i]] = i idxR[i] = S[i] L = len(idx) UF = UnionFind(L) left = list(range(L)) right = list(range(L)) visited = [False]*L ans = [] MAX = 1 for A, B in AB: l, r = idx[A], idx[B] visited[l] = True if 1 <= l and visited[l-1] and not UF.same(l-1, l) and idxR[l]-idxR[l-1] == 1: nl = left[UF.leader(l-1)] nr = right[UF.leader(l)] UF.merge(l-1, l) left[UF.leader(l)] = nl right[UF.leader(l)] = nr MAX = max(MAX, idxR[right[UF.leader(l)]]-idxR[left[UF.leader(l-1)]]+1) l = right[UF.leader(l)] while l < r: visited[l+1] = True nl = left[UF.leader(l)] nr = right[UF.leader(l+1)] UF.merge(l, l+1) left[UF.leader(l)] = nl right[UF.leader(l)] = nr l = nr MAX = max(MAX, idxR[right[UF.leader(l)]]-idxR[left[UF.leader(l)]]+1) if r < L-1 and visited[r+1] and not UF.same(r, r+1) and idxR[r+1]-idxR[r] == 1: nl = left[UF.leader(r)] nr = right[UF.leader(r+1)] UF.merge(r, r+1) left[UF.leader(r)] = nl right[UF.leader(r)] = nr MAX = max(MAX, idxR[right[UF.leader(r)]]-idxR[left[UF.leader(r)]]+1) ans.append(MAX) print(*ans, sep="\n")