Background

Problem Description

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$.

Input Format

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 Format

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

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

3 3 5 5 5

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

8 8 7 7 5 4 3 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

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

Hint

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