# LCA and Distance
## Problem Statement
You are given a tree with $n$ nodes, numbered from $1$ to $n$. The tree is rooted at node $1$. You need to process $q$ queries. Each query consists of two distinct nodes, $u$ and $v$. For each query, you must find two values:
1. The Lowest Common Ancestor (LCA) of nodes $u$ and $v$.
2. The distance between nodes $u$ and $v$. The distance is defined as the number of edges on the unique simple path connecting $u$ and $v$.
## Input Format
- The first line contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$) — the number of nodes in the tree and the number of queries.
- The next $n-1$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) — representing an edge connecting node $u_i$ and node $v_i$. These $n-1$ edges are guaranteed to form a tree.
- The next $q$ lines each contain two integers $u_j$ and $v_j$ ($1 \le u_j, v_j \le n$, $u_j \ne v_j$) — representing the nodes for the $j$-th query.
## Output Format
For each query, print two space-separated integers on a new line: the LCA of $u$ and $v$, followed by the distance between $u$ and $v$.
## Sample Test Cases
### Sample Input 1
```
5 3
1 2
1 3
2 4
2 5
4 5
3 5
1 2
```
### Sample Output 1
```
2 2
1 3
1 1
```
### Sample Input 2
```
5 3
1 2
2 3
3 4
4 5
1 5
2 4
3 5
```
### Sample Output 2
```
1 4
2 2
3 2
```
## Constraints
- $1 \le n, q \le 10^5$
- $1 \le u_i, v_i \le n$ for edges
- $1 \le u_j, v_j \le n$ for queries
- $u_i \ne v_i$ for edges, $u_j \ne v_j$ for queries
- The given edges form a valid tree.
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
For Sample Input 1:
- Query $(4, 5)$: Nodes $4$ and $5$ are children of node $2$. Their Lowest Common Ancestor is $2$. The path from $4$ to $5$ is $4-2-5$, which consists of $2$ edges, so the distance is $2$.
- Query $(3, 5)$: Node $3$ is connected to $1$. Node $5$ is connected to $2$, which is connected to $1$. The common ancestor closest to both $3$ and $5$ is $1$. The path from $3$ to $5$ is $3-1-2-5$, which consists of $3$ edges, so the distance is $3$.
- Query $(1, 2)$: Node $1$ is the parent of node $2$. Their Lowest Common Ancestor is $1$. The path from $1$ to $2$ is $1-2$, which consists of $1$ edge, so the distance is $1$.
Loading problem statement...