"Money money MONEY, I want money" thought Alex. "Now how do I get money? Well... I'll open up a camp!"

Well, unfortunately things didn't go so well for Alex's campers, and now there are N campers wandering around the city aimlessly. You have to handle Q queries; which consist of two groups finding each other and becoming one larger group. After each query, output the difference between the group of largest size and group of smallest size. If there is only one group, output 0. At first, everyone is in their own group.

Also note, if the two campers in the query are already in the same group, print the current answer, and skip merging the groups together.

Input:

The first line consists of two space separated integers, N and Q

The next Q line consists of two integers, A and B, meaning that the groups involving camper A and camper B find each other.

Output:

Output Q lines, the answer after each query. 

Constraints:

1 ≤ N ≤ 10^5

1 ≤ Q ≤ 10^5

SAMPLE INPUT
2 1
1 2

SAMPLE OUTPUT
0

Explanation

Here, the two campers find each other, so the answer is 0.
def union(parents, depths, i, j):
    ''' Union with under the deepest root '''
    if depths[i] > depths[j]:
        parents[j] = i
    else:
        parents[i] = j
        depths[i] = max(depths[i], depths[j] + 1)

def find(parents, el):
    ''' Find an element and compress the sets '''
    if parents[el] == el: return el
    leader = find(parents, parents[el])
    parents[el] = leader
    return leader

def solve(n, xss):
    depths = [1] * n
    parents = range(0, n)
    group_sizes = [1] * n
    count_group_of_size = [0] * (n + 1)
    count_group_of_size[1] = n
    smaller_index = 1
    maxi = 1
    res = []
    for a, b in xss:
        root_a = find(parents, a - 1)
        root_b = find(parents, b - 1)
        if root_a != root_b:
            union(parents, depths, root_a, root_b)
            count_group_of_size[group_sizes[root_a]] -= 1
            count_group_of_size[group_sizes[root_b]] -= 1
            new_size = group_sizes[root_a] + group_sizes[root_b]
            group_sizes[root_a] = new_size
            group_sizes[root_b] = new_size
            count_group_of_size[new_size] += 1
            maxi = max(maxi, new_size)
            while count_group_of_size[smaller_index] == 0: smaller_index += 1
        res.append(str(maxi - smaller_index))
    return '\n'.join(res)

if __name__ == '__main__':
    n, q = map(int, raw_input().split())
    xss = [map(int, raw_input().split()) for _ in range(q)]
    print solve(n, xss)