Update appNew update is available. Click here to update.

Sum of Distance

Posted: 11 Mar, 2021
Difficulty: Hard


Try Problem

You are given an undirected unweighted graph such that there are no loops in this graph and it is strongly connected and there are always (vertices-1) edges in the graph. For each node, you need to find the sum of the distance of all other nodes from the given node.

Distance between any two nodes is the number of edges between the two given nodes.

Input Format:
The first line of input contains an integer 'T', the number of test cases.

The first line of the test case contains a single integer ‘N’.

From the second line onwards next 'N-1' lines denote the edges of the graph.

Each edge is characterized by two integers  'A' and 'B' where 'A' and 'B' denote the endpoints of the edge. The edges[i][0], edges[i][1] contains the endpoints of edges.
Output Format:
For each test case, return the list where the ith element denotes the distance of the ith vertex from all others vertices.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 50
1 <= N <= 10^3
0 <= edges[i][0], edges[i][1] <= N-1  
Total number of edges = N-1

Time Limit: 1 sec