Combination of Problem Ideas

Small Qiang has prepared M unique ideas. Initially, each idea forms a problem; that is, the first M problems each correspond to a distinct idea. Then, some problems are generated by combining two existing problems. When two problems A and B are combined, the resulting problem covers all the ideas that appear in A or B, i.e., the union of their idea sets. This combination process can be performed repeatedly.

For example, if there are three original ideas corresponding to problems P₁, P₂, and P₃:

• Combining P₁ and P₂ produces P₄ with ideas \(\{1,2\}\).
• Combining P₂ and P₃ produces P₅ with ideas \(\{2,3\}\).
• Combining P₄ and P₅ produces P₆ with ideas \(\{1,2,3\}\).

Your task is to determine, for each problem, the number of distinct ideas it involves. Note that if an idea appears more than once when combining problems, it should only be counted once.

Formal description: If problem A covers idea set \(S_A\) and problem B covers idea set \(S_B\), then the combined problem covers \(S_A \cup S_B\). Output the size of this set for every problem.

inputFormat

The first line contains two integers N and M where:

• N is the total number of problems.
• M is the number of original problems (each corresponding to a unique idea).

The next N - M lines describe the composite problems. Each of these lines contains two integers a and b (with 1 ≤ a, b < current problem index) indicating that the current problem is formed by combining problem a and problem b.

Note: For problems 1 to M, no additional data is provided since they are the original problems.

outputFormat

Output N lines. The i-th line should contain a single integer representing the number of distinct ideas involved in problem i.

sample

6 3
1 2
2 3
4 5

1
1
1
2
2
3