Best Possible River Ranking

The Chao Phraya River System in Thailand exhibits an interesting phenomenon at confluences where two or more rivers meet. At a confluence (other than the sea, which is given the special label 0), one must choose one of the incoming river names for the merged river. This decision determines how much of each river's length is credited to it.

For example, assume two rivers meet at a confluence. Suppose river A contributes a length of 305 km up to the confluence and river B contributes 335 km up to the same confluence. There is also an edge of 353 km after the confluence leading to the sea. If the decision is made to carry on with the name of river A then river A’s final length becomes \[ 305+353=658\mbox{ km}, \] while river B’s length is only 335 km. On the other hand, if river B’s name is chosen then its final length becomes \[ 335+353=688\mbox{ km}, \] with river A’s final credited length being only 305 km.

In a given river network the water flows from various sources (which never receive water from other rivers) downstream towards the sea (labeled 0). Every river follows a unique path from its source to the sea. At each confluence (a node with at least two incoming river segments) a decision is made: the continuing river must take one of the incoming names. Therefore, any river can have its final credited length vary between two extremes:

• Maximum length: If at every confluence that the river is part of the decision is made in its favor, then its credited length is the sum of all segments along its entire path from source to sea.
• Minimum length: If, at the very first confluence it reaches (if any), a different name is chosen then the credited length is only the distance from its source up to that confluence (the drop‐off point). Note that if a river flows directly to the sea without meeting any confluence (other than 0), its minimum length equals its maximum length.

The rank of a river is defined by ordering all rivers in decreasing order of their final credited lengths. The best (highest) rank is 1. When there is a tie (equal lengths), all tied rivers receive the best (smallest) rank among them. In order to settle disputes among the towns along the rivers, your task is to determine, for each river, its best possible rank over all naming schemes. More precisely, for each river you are to assume a naming scheme that:

1. Favors that river throughout its entire path (so that its credited length is the maximum possible),
2. And simultaneously minimizes the credited lengths of all other rivers (by dropping their names at the first possible confluence).

You are given the entire river network as a collection of river segments. Each segment is described by three integers u, v, and d meaning that there is a river segment from node u to node v with length d kilometers. The water flows from a source towards the sea (node 0). Every node (except 0) appears as the start of at most one segment; however, a node may have two or more incoming segments. A node with no incoming segment is a source (and its river bears a unique name). Note that the sea (node 0) is not a confluence. For each source, compute its best possible rank when compared with all other sources.

Input Format:

The input begins with an integer T which is the number of river segments in the network. Each of the next T lines contains three integers u, v, d representing a river segment from node u to node v with length d. (Note: v may be 0 indicating the sea.)

Output Format:

For each river source (in increasing order of node number), output a single line containing one integer — the best possible rank of that river when compared to all other rivers under an optimal naming scheme as described. The rank is defined as 1 plus the number of other rivers which, even after being minimized, have a credited length strictly greater than the maximum possible credited length of the river.

Note: If two or more rivers are tied (i.e. they have equal credited lengths) they are considered to share the best (smallest) rank.

inputFormat

The first line contains a single integer T, the number of river segments.

Each of the next T lines contains three space‐separated integers u, v, d, indicating that there is a river segment from u to v with length d. Here, v = 0 denotes the sea. It is guaranteed that every node (except 0) is the start of at most one segment. Nodes that never appear as a destination (v) are the river sources.

Example:

7
101 0 765
102 0 740
103 0 700
104 1 305
105 1 335
1 0 353
106 0 513

This describes a river system with 6 sources (101, 102, 103, 104, 105, 106) and one confluence (node 1) where rivers 104 and 105 meet.

outputFormat

For each river source (in increasing order by node number), output its best possible rank on a separate line.

Example Output corresponding to the above Example Input:

1
2
3
4
4
4

sample

7
101 0 765
102 0 740
103 0 700
104 1 305
105 1 335
1 0 353
106 0 513

1
2
3
4
4
4

</p>