Reversing the Boat Routes

Waldives consists of \(N\) islands numbered from \(0\) to \(N-1\). There are \(N-1\) one‐way boat routes connecting these islands such that they form a tree. Due to their one-way nature, many islands are unreachable from one another. In order to achieve strong connectivity (i.e. every island can reach every other island), the government wants to build a minimum number of new bus routes.

Each new bus route must satisfy the following conditions:

1. The bus route corresponds to a contiguous path in the tree (i.e. a simple path). The bus route covers a sequence of one or more boat routes (i.e. the tree edges) that lie consecutively along that path.
2. Within a bus route, each boat route (tree edge) is covered at most once.
3. For every boat route covered by the bus route, the direction of travel on the bus route is opposite to that of the boat route. In other words, if a boat route goes from \(u\) to \(v\) (i.e. \(u \to v\)), then when it is covered by a bus route the corresponding segment must go from \(v\) to \(u\).
4. Different bus routes may cover the same boat routes or islands.

The task is: Given the information of the boat routes, determine the minimum number of bus routes that need to be built such that the resulting transportation network is strongly connected. It can be shown that the answer is \(\max(s, t)\) where \(s\) is the number of islands with no incoming boat route and \(t\) is the number of islands with no outgoing boat route.

Formally, let the boat route network be a directed tree (with \(N\) nodes and \(N-1\) edges). For each island, let in-degree be the number of boat routes arriving at that island and out-degree be the number of boat routes leaving that island. Then the minimal number of bus routes required is:

[ \text{answer} = \max\Big(|{ i : \text{in-degree}(i)=0 }|,; |{ i : \text{out-degree}(i)=0 }|\Big). ]

inputFormat

The first line contains an integer \(N\) \((1 \leq N \leq 10^5)\), the number of islands.
The following \(N-1\) lines each contain two integers \(u\) and \(v\) \((0 \leq u,v < N)\), indicating a one‐way boat route from island \(u\) to island \(v\).

outputFormat

Output a single integer: the minimum number of bus routes needed to make the entire network strongly connected.

sample

2
0 1

1