圣诞节到了，小基准备在他花园里的大树上布置若干灯泡庆祝节日。小基的大树的形状类似于树这种数据结构。

大树由若干分支节点和叶子节点组成，一共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个灯泡，明显不存在灯泡更多的方案。

对于所有测试数据有：$1\le n\le2\times{10}^5$。