Courageous Paths in an Inward Base-Cycle Tree

Given a functional directed graph of n nodes that forms an inward base‐cycle tree (i.e. a functional graph which is weakly connected with exactly one cycle, where each node i has a directed edge to node f(i) with an associated weight), and a special parameter k (k ≥ 1), we define the following.

For any vertex x, note that due to the direction of the given edges some nodes might not be reachable from x in the original graph. However, by reversing some edges you can make x reach every other vertex. When traveling from x to some vertex y, you are allowed to traverse edges in the forward (given) direction at no cost, and you may also traverse an edge in the reverse direction at a cost of 1 (i.e. you “flip” the edge). We define a valid path from x to y to be one that minimizes the number of reversed edges needed in order for x to reach y.

If the minimum number of reversed edges required for x to reach y is at least k, then we call y a courageous point of x. On the chosen minimal reversal path from x to y, let
\( F(x,y) \) be the sum of weights on all forward (non‐reversed) edges, and
\( R(x,y) \) be the sum of weights on all reversed edges. We then define the wave value
\( G(x,y)= F(x,y)\times R(x,y)\).

Your task is: For every vertex i (1 ≤ i ≤ n), compute
\( S(i)=\sum_{y \text{ is a courageous point of } i} G(i,y) \),
where the summation runs over every vertex y (other than i) for which the minimum number of reversed edges is at least k (note that if y = i, the path is trivial and uses 0 reversed edges and will not be counted).

Input Format: The graph is given in a functional form. The first line contains two integers, n and k. Then n lines follow; the i-th line contains two integers f and w, representing that there is a directed edge from node i to node f with weight w. It is guaranteed that the resulting graph is weakly connected and forms an inward base‐cycle tree.

Note: You can assume that nodes are numbered from 1 to n.

inputFormat

The first line contains two integers n and k (1 ≤ n ≤ small constrained, k ≥ 1).

Each of the next n lines contains two integers f and w where there is a directed edge from the current node (the i-th node) to node f with weight w.

outputFormat

Output n lines. The i-th line should contain a single integer representing the sum of G(i, y) over all courageous points y of node i.

sample

3 1
2 5
3 7
2 2

0
0
10