Question
Tree Numbering
You are given a tree with N vertices numbered from 1 to N and N-1 edges the ith of which means that there is an edge between Ai and Bi.
For each x from 1 to N, do the following operation.
Initially all the nodes are numberless. Write number 1 on node x. Choose a node and write a unique number (from 2 to N) on it. You can only choose a node and give it a number if it is adjacent to a node that already has a number on it.
Find the number of ways in which we can write the numbers on the nodes, modulo (10^9+7)
For each x from 1 to N, do the following operation.
Initially all the nodes are numberless. Write number 1 on node x. Choose a node and write a unique number (from 2 to N) on it. You can only choose a node and give it a number if it is adjacent to a node that already has a number on it.
Find the number of ways in which we can write the numbers on the nodes, modulo (10^9+7)
Input
The first line of the input contains a single integer N
The next N-1 lines contains 2 integers Ai and Bi (denoting an edge between Ai and Bi)
Constraints:
2 <= N <=2 × 105
1 <= Ai, Bi <= N
The given undirected graph is a tree.
The next N-1 lines contains 2 integers Ai and Bi (denoting an edge between Ai and Bi)
Constraints:
2 <= N <=2 × 105
1 <= Ai, Bi <= N
The given undirected graph is a tree.
Output
For each k = 1, 2,. N print the corresponding answer to the problem
Example
Sample Input 1:
3
1 2
1 3
Sample Output 1:
2
1
1
Sample Input 2:
2
1 2
Sample Output 2:
1
1
Sample Input 3:
5
1 2
2 3
3 4
3 5
Sample Output 3:
2
8
12
3
3
3
1 2
1 3
Sample Output 1:
2
1
1
Sample Input 2:
2
1 2
Sample Output 2:
1
1
Sample Input 3:
5
1 2
2 3
3 4
3 5
Sample Output 3:
2
8
12
3
3