P10573 [JRKSJ R8] C0mp0nents

  

Little I has an undirected graph with $n$ vertices and $m$ edges. It is guaranteed that the graph has no multiple edges and no self-loops. Initially, the vertex weight of vertex $i$ is $a_i = i$. Little I also has an extra constant $k$. Little R can perform a very large number of operations. In each operation, she chooses two adjacent vertices $x, y$ 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$, **without modifying the weight of the vertex $\bm x$ where $\bm{a_x = s}$ during the process**, Little I wants to know: after some operations, what is the maximum number of vertices in the graph that can satisfy $a_i = s$.

The first line contains three integers $n, m, k$. The next $m$ lines each contain two integers $u, v$, indicating an edge connecting $u, v$.

Output one line with $n$ integers. The $i$-th integer is the answer for $s = i$.

### Constraints **This problem uses bundled testdata.** - Subtask 0 (0 pts): samples. - 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 limits. For all testdata: $1 \leq k \leq n \leq 4\times 10^5$, $1 \leq u, v \leq n$, $0 \leq m \leq 10^6$. It is guaranteed that the graph has no multiple edges and no self-loops. Translated by ChatGPT 5