Problem 1201. -- Friends

## 1201: Friends

Time Limit: 1 Sec  Memory Limit: 1280 MB
Submit: 153  Solved: 42
[Submit][Status][Web Board]

## Description

In a country, the relationship between people can be indicated by a tree. If two people are acquainted with each other, there will be an edge between them. If a person can get in touch with another through no more than five people, we should consider these two people can become friends. Now, give you a tree of N people’s relationship. ( 1 <= N <= 1e5), you should compute the number of who can become friends of each people?

## Input

In the first line, there is an integer T, indicates the number of the cases.
For each case, there is an integer N indicates the number of people in the first line.

In the next N-1 lines, there are two integers u and v, indicate the people u and the people

v are acquainted with each other directly. People labels from 1.

## Output

For each case, the first line is “Case #k :”, k indicates the case number.

In the next N lines, there is an integer in each line, indicates the number of people who can become the ith person’s friends. i is from 1 to n.

## Sample Input

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



## Sample Output

Case #1:
6
7
7
7
7
7
7
6


[Submit][Status]