Graph Label Propagation

You are given an undirected graph with (n) vertices and (m) edges (no self‐loops and no multiple edges). Initially, the weight (or label) of vertex (i) is (a_i = i). In addition, you are given an integer constant (k).

In each operation, you may choose two adjacent vertices (x) and (y) such that [ |a_x - a_y| = k, ] and then set (a_x = a_y). You may perform as many operations as you want (possibly zero).

For every (s) with (1 \le s \le n), assume that the vertex whose initial weight is (s) (the "anchor") is never updated. Under this constraint, determine the maximum number of vertices that can have weight (s) after some sequence of operations.

\textbf{Note:} The only vertices (apart from the anchor) that can possibly be updated to (s) are those (x) for which the condition (|x - s| = k) holds. However, even if (x) satisfies (|x - s| = k), it can only be updated if there is a path in the original graph from the anchor vertex (s) to (x) in a special induced subgraph. The allowed vertices in this induced subgraph are only the anchor (s) and the vertices with index (s+k) or (s-k) (if they exist). An edge between any two vertices in this set is present if and only if it exists in the original graph. The answer for each (s) is the size of the connected component containing (s) (in the induced subgraph), which is at most 3 (when (k > 0) because there is exactly one possible vertex with value (s+k) and one with (s-k)). For (k=0) the only vertex available is (s) itself.

Formally, for each (s):
(\texttt{ans}s = 1 + \mathbf{1}{(s+k\ \text{exists and is connected to } s)} + \mathbf{1}_{(s-k\ \text{exists and is connected to } s)}),
where connectivity means either a direct edge from (s) to the candidate vertex or an indirect connection via the other candidate vertex (if both candidates exist).

inputFormat

The first line contains three integers (n), (m), and (k). Each of the next (m) lines contains two integers (u) and (v) ((1 \le u, v \le n)) representing an edge between vertices (u) and (v).

outputFormat

Output (n) integers. The (s)-th integer is the maximum number of vertices that can have weight (s) after performing some operations, under the condition that the vertex initially with weight (s) remains unchanged. The numbers can be printed on one line separated by spaces.

sample

5 3 2
1 3
3 5
2 4

2 2 3 2 2