圣诞节到了，小基准备在他花园里的大树上布置若干灯泡庆祝节日。小基的大树的形状类似于树这种数据结构。 大树由若干分支节点和叶子节点组成，一共n个节点，编号为1~n，其中编号为1的节点是根节点，小基希望在这些节点中选择若干节点，每个节点上放一个灯泡。 小基希望所有叶子节点到根节点的每条简单路径上，灯泡数量均为3的倍数，以表他对耶稣的崇拜。 求小基最多可以放多少灯泡。

从文件tree.in中读入数据。每个测试点包含多组测试数据。 输入的第一行是一个正整数n，表示树的节点的数量。 接着n-1行，每行两个个数字u、v，表示节点u和节点v之间有一条边。

输出到文件tree.out中。 输出仅一个数字，为最大的灯泡数量。

树的形状如下图。

最优方案为1、2、3中任选2个放置灯泡，4、6中任选1个放置灯泡，7、8中任选1个放置灯泡，5必须放置灯泡，这样使得1-6、1-5、1-7的树上简单路径上均有3个灯泡。总计5个灯泡，明显不存在灯泡更多的方案。

青少年编程挑战赛