# Tree Coloring with Extended Adjacency
## Problem Statement
You are given a tree with $n$ nodes and $n-1$ edges. Your task is to color each node such that two conditions are met:
1. No two adjacent nodes have the same color. That is, if an edge $(u,v)$ exists, then $color(u) \neq color(v)$.
2. No two nearly-adjacent nodes have the same color. Two distinct nodes $u$ and $w$ are considered nearly-adjacent if there exists a common neighbor $v$ such that $(u,v)$ and $(v,w)$ are edges. In this case, $color(u) \neq color(w)$.
You need to find the minimum number of colors required to satisfy these conditions.
Consider a node $u$. According to condition 1, $u$ must have a different color from all its direct neighbors. According to condition 2, any two distinct neighbors of $u$ (say $v_1$ and $v_2$) must also have different colors, as they are both adjacent to the common node $u$. This implies that the node $u$ and all its $\text{deg}(u)$ neighbors must all have distinct colors. Therefore, at least $\text{deg}(u) + 1$ colors are required for the subgraph induced by $u$ and its neighbors. To satisfy the conditions for the entire tree, we must use at least $\max_{u \in V} (\text{deg}(u) + 1)$ colors. It can be shown that this number of colors is always sufficient for any tree.
## Input Format
- First line: $n$ ($1 \le n \le 10^5$) - The number of nodes in the tree.
- Next $n-1$ lines: Two integers $u, v$ ($1 \le u, v \le n$) - Representing an edge between node $u$ and node $v$.
## Output Format
Print a single integer, the minimum number of colors required.
## Sample Test Cases
### Sample Input 1
```
4
1 2
4 3
2 3
```
### Sample Output 1
```
3
```
### Sample Input 2
```
5
1 2
1 3
1 4
1 5
```
### Sample Output 2
```
5
```
## Constraints
- $1 \le n \le 10^5$
- $1 \le u, v \le n$
- The given graph is guaranteed to be a tree.
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
For Sample Input 1:
The tree has 4 nodes. The edges are (1,2), (4,3), (2,3).
The degrees of the nodes are:
- $\text{deg}(1) = 1$ (connected to 2)
- $\text{deg}(2) = 2$ (connected to 1, 3)
- $\text{deg}(3) = 2$ (connected to 4, 2)
- $\text{deg}(4) = 1$ (connected to 3)
The maximum degree in the tree is $\Delta = 2$.
As explained in the problem statement, the minimum number of colors required is $\Delta + 1 = 2 + 1 = 3$.
For Sample Input 2:
The tree has 5 nodes. Node 1 is connected to nodes 2, 3, 4, and 5. This is a star graph.
The degrees of the nodes are:
- $\text{deg}(1) = 4$ (connected to 2, 3, 4, 5)
- $\text{deg}(2) = 1$ (connected to 1)
- $\text{deg}(3) = 1$ (connected to 1)
- $\text{deg}(4) = 1$ (connected to 1)
- $\text{deg}(5) = 1$ (connected to 1)
The maximum degree in the tree is $\Delta = 4$.
The minimum number of colors required is $\Delta + 1 = 4 + 1 = 5$.
Loading problem statement...