#GYM104768A. Easy Diameter Problem
Easy Diameter Problem
本题没有可用的提交语言。
Description
Randias is given a tree with $n$ vertices. He does the following operation until the tree contains $0$ vertices:
- choose a vertex which is an endpoint of any diameter, and then remove it.
He asks you to find the number of removal orders modulo $10^9+7$.
Note that two orders are considered different if and only if there exists $i$ ($1\le i\le n$), where the $i$-th vertex being removed in one order is different from the $i$-th vertex being removed in the other order.
Recall that a vertex $u$ is an endpoint of some diameter if there exists a vertex $v$ such that $\texttt{dis}(u,v)\ge \texttt{dis}(i,j)$ for any pair of vertices $i$ and $j$, where $\texttt{dis}(x,y)$ represents the number of edges in the shortest path from $x$ to $y$.
The first line contains one integer $n$ ($1\le n \le 300$), denoting the number of vertices of the tree.
The following $n-1$ lines, each line contains two integers $u$ and $v$ ($1\le u,v\le n$, $u\ne v$), denoting an edge connecting $u$ and $v$.
It is guaranteed that the edges form a tree.
Print a single integer, denoting the number of removal orders modulo $10^9 + 7$.
Input
The first line contains one integer $n$ ($1\le n \le 300$), denoting the number of vertices of the tree.
The following $n-1$ lines, each line contains two integers $u$ and $v$ ($1\le u,v\le n$, $u\ne v$), denoting an edge connecting $u$ and $v$.
It is guaranteed that the edges form a tree.
Output
Print a single integer, denoting the number of removal orders modulo $10^9 + 7$.
3
1 2
3 2
5
4 1
4 5
1 2
1 3
7
5 7
2 5
2 1
1 6
3 6
4 1
4
28
116
Note
For the first example, $[1,2,3]$, $[1,3,2]$, $[3,1,2]$, $[3,2,1]$ are possible removal orders.