You are provided a weighted tree that consists of $n$ nodes. For each edge of the tree, print the number of diameters that is a part of an edge. Note:

• Diameter is the longest path in the tree.
• The edges are numbered in the same order as they are mentioned in the sample input.

Input format

The first line of the input consists of an integer $n$ that is followed by $n-1$ lines. Each line consists of three space-separated integers, $a$, $b$, and $c$. These space-separated integers denote an edge between nodes $a$ and $b$ that weighs $c$.

Output format

For each edge of the tree (in the order they are mentioned in the sample input), print the total number of diameters that is a part of an edge.

Constraints

$1\leq n\leq 10^5$

$1\leq a,b\leq n$

$a\neq b$

$0\leq c\leq 10^9$