#S1011. [POI2014]Hotel加强版
[POI2014]Hotel加强版
题目描述
有一个树形结构的宾馆, 个房间, 条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意?
输入格式
第一行一个数 。
接下来 行,每行两个数 ,表示 和 之间有一条边相连。
输出格式
让吉丽满意的方案数。
样例输入
7
1 2
5 7
2 5
2 3
5 6
4 5
样例输出
5
样例说明
方案分别为 。
数据规模与约定
对于 的数据,,。