Problem Background

• update: The problem statement for D has been modified to include the phrase if the weight of node $\bm{a_x = s}$ is not modified during the process.
• update 2: The problem statement for D has been (secondly) modified to if the weight of node $\bm{a_x = s}$ is not modified during the process.

Problem Description

Little I has an undirected graph with $n$ vertices and $m$ edges, ensuring that the graph has no duplicate edges or self-loops. Initially, the weight of the $i$-th vertex is $a_i = i$. Little I has an additional constant $k$.

Little R can perform many operations. Each operation involves selecting two adjacent vertices $x$ and $y$ in the graph such that $\lvert a_x - a_y \rvert = k$, and then Little I sets $a_x$ to $a_y$.

For each $1 \leq s \leq n$, if the weight of node $\bm{a_x = s}$ is not modified during the process, Little I wants to know: after several operations, what is the maximum number of vertices in the graph that satisfy $a_i = s$.

Input Format

The first line contains three integers $n$, $m$, and $k$.

The next $m$ lines each contain two integers $u$ and $v$, representing an edge connecting vertices $u$ and $v$.

Output Format

One line containing $n$ integers, where the $i$-th integer represents the answer when $s = i$.

Sample Input and Output

Sample Input #1

5 6 1
1 2
1 3
1 5
2 3
2 4
4 5

Sample Output #1

3 3 5 5 5

Sample Input #2

8 10 1
1 3
1 4
1 5
2 3
2 7
3 6
4 6
5 8
6 7
7 8

Sample Output #2

8 8 7 7 5 4 3 3

Sample Input #3

14 19 2
1 3
1 4
1 9
2 5
2 14
3 7
4 5
4 6
4 7
4 8
5 6
5 11
6 8
7 9
8 10
8 12
9 10
10 11
11 12

Sample Output #3

2 1 2 4 1 4 2 4 2 5 1 5 1 1

Notes

Data Size and Constraints

This problem uses batched testing.

• Subtask 0 (0 pts): Examples;
• Subtask 1 (5 pts): $n \leq 200$, $m \leq 400$;
• Subtask 2 (20 pts): $n \leq 5000$, $m \leq 10^4$;
• Subtask 3 (25 pts): $n \leq 10^5$, $m \leq 3 \times 10^5$;
• Subtask 4 (50 pts): No special restrictions.

For all data, $1 \leq k \leq n \leq 4 \times 10^5$, $1 \leq u, v \leq n$, $0 \leq m \leq 10^6$, ensuring that the graph has no duplicate edges or self-loops.

见题面 Input 部分

见题面 Output 部分