Longest Monochromatic Path in a Tree

You are given a tree with \( n \) nodes numbered from \( 1 \) to \( n \) and \( n - 1 \) edges. Initially, each node is colored white. We then perform \( q \) operations. In each operation, two vertices \( u \) and \( v \) are given, and all nodes along the unique simple path from \( u \) to \( v \) (inclusive) are colored black. A simple path in a tree is a path that does not contain any vertex more than once.

After each operation, determine the length of the longest simple path in the tree such that all nodes on the path have the same color. The length of a path is defined as the number of nodes on that path.

Note: The longest path can be entirely composed of white nodes or entirely composed of black nodes.

inputFormat

The first line contains an integer \( n \) denoting the number of nodes in the tree. Each of the next \( n - 1 \) lines contains two integers \( u \) and \( v \) indicating an edge between nodes \( u \) and \( v \). The next line contains an integer \( q \) denoting the number of operations. Each of the next \( q \) lines contains two integers \( u \) and \( v \), representing an operation where the simple path between \( u \) and \( v \) is colored black.

Constraints: You may assume that \( n \) and \( q \) are small enough for a simulation based solution to run within the time limits.

outputFormat

For each operation, output a single integer: the length of the longest simple path in the tree where all nodes on the path have the same color.

sample

5
1 2
2 3
3 4
4 5
3
1 3
2 5
3 3

3
3
3