Assign Tree Values with Absolute Difference Constraints

You are given a tree with n nodes and an integer g. Your task is to assign each node a unique integer from 1 to n such that for every edge connecting two nodes i and j, the following condition holds:

$|v_i - v_j| \ge g$

If such an assignment is possible, output the assignment in the order of node numbers from 1 to n. Otherwise, output -1.

Note: The tree is given as an undirected graph with n - 1 edges.

inputFormat

The input is given via stdin and has the following format:

n g
u1 v1
u2 v2
... (n-1 lines)

Here, n is the number of nodes, g is the minimum required absolute difference, and each of the next n - 1 lines contains two integers u and v indicating an undirected edge between nodes u and v.

outputFormat

The output should be printed to stdout. If a valid assignment exists, print the assigned values for nodes 1 through n separated by spaces on a single line. If no valid assignment exists, print -1.

5 1
1 2
1 3
2 4
3 5

1 2 3 4 5