Gery got "_Compilation Error_" because he forgot to include the C++ standard header _cstring_. So he lost all the score of three problems. One of the problems is:
There is a tree with $n$ verticies. $m$ queries would be performed on it. Each query contains two parameters $u$ and $v$. You should calculate $$\sum_{r=1}^n d_r(u, v)$$
$d_r (u, v)$ is the _beautifulness_ of the road from vertex $u$ to vertex $v$ in the tree, with vertex $r$ as the root.
With vertex $r$ as the root, the _beautifulness_ of the road from $u$ to $v$ is defined
$$d_r(u, v) = dis(u,lca_r(u,v)) \times dis(v,lca_r(u,v))$$
$d i s (u, v)$ is the direct distance between $u$ and $v$, and $l c a_r (u, v)$ is the least common ancestor of $u$ and $v$, with $r$ as the root.
Originally the constraint of this problem was $1 <= n, m <= 1000$. But Gery was in a bad mood so he fortified the problem. The constraint is now $1 <= n, m <= 10^5$.
Help the Orz Pandas to solve this problem so they would be able to access https://gery.top.
There is only one test case in the input file.
The first line contains two integers $n$ and $m$ . The $i$-th of the following $n -1$ lines contains two integers $x_i$ and $y_i$, the vertices connected by the $i$-th edge. Each of the following $m$ lines contains a pair of integers, $u$ and $v$, the pair of vertices being queried.
It's guaranteed that $1 <= n, m <= 10^5$, and $1 <= x_i, y_i, u, v <= n$.
For each query, output one line containing the answer of the query, modulo $998244353$.
For the second query, we have $d_1 (2, 5) = d i s (2, 1) times d i s (5, 1) = 2$, $d_2 (2, 5) = d i s (2, 2) times d i s (5, 2) = 0$, $d_3 (2, 5) = d i s (2, 3) times d i s (5, 3) = 2$, $d_4 (2, 5) = d i s (2, 3) times d i s (5, 3) = 2$, and $d_5 (2, 5) = d i s (2, 5) times d i s (5, 5) = 0$. Their sum is $6$.
## Input
There is only one test case in the input file.The first line contains two integers $n$ and $m$ . The $i$-th of the following $n -1$ lines contains two integers $x_i$ and $y_i$, the vertices connected by the $i$-th edge. Each of the following $m$ lines contains a pair of integers, $u$ and $v$, the pair of vertices being queried.It's guaranteed that $1 <= n, m <= 10^5$, and $1 <= x_i, y_i, u, v <= n$.
## Output
For each query, output one line containing the answer of the query, modulo $998244353$.
[samples]
## Note
For the second query, we have $d_1 (2, 5) = d i s (2, 1) times d i s (5, 1) = 2$, $d_2 (2, 5) = d i s (2, 2) times d i s (5, 2) = 0$, $d_3 (2, 5) = d i s (2, 3) times d i s (5, 3) = 2$, $d_4 (2, 5) = d i s (2, 3) times d i s (5, 3) = 2$, and $d_5 (2, 5) = d i s (2, 5) times d i s (5, 5) = 0$. Their sum is $6$.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the initial number of paper balls.
Let $ A = \{a_1, a_2, \dots, a_m\} \subset \mathbb{Z}^+ $ be Long Long's move set.
Let $ B = \{b_1, b_2, \dots, b_m\} \subset \mathbb{Z}^+ $ be Mao Mao's move set.
**Constraints**
1. $ 1 \le n \le 5000 $
2. $ 1 \le m \le 100 $
3. $ 1 \le a_i < a_{i+1} \le 500 $ for all $ i \in \{1, \dots, m-1\} $
4. $ 1 \le b_i < b_{i+1} \le 500 $ for all $ i \in \{1, \dots, m-1\} $
**Objective**
Determine the winner of the impartial game under normal play convention, where:
- Players alternate turns, starting with Long Long.
- On a turn, a player may remove $ x $ paper balls iff $ x \in $ their respective set ($ A $ for Long Long, $ B $ for Mao Mao).
- A player unable to move loses.
Compute the Grundy number (nimber) $ g(k) $ for each state $ k \in \{0, 1, \dots, n\} $:
$$
g(0) = 0
$$
$$
g(k) = \text{mex}\left( \{ g(k - x) \mid x \in A \text{ and } x \le k \} \right) \quad \text{for } k \ge 1 \text{ (Long Long's turn)}
$$
$$
g(k) = \text{mex}\left( \{ g(k - x) \mid x \in B \text{ and } x \le k \} \right) \quad \text{for } k \ge 1 \text{ (Mao Mao's turn)}
$$
But since moves depend on **whose turn it is**, this is a **partisan game**. Define:
- $ W(k) = \text{True} $ if the current player (starting with Long Long) can force a win from state $ k $, else False.
Recurrence:
$$
W(0) = \text{False}
$$
For $ k \ge 1 $:
$$
W(k) =
\begin{cases}
\bigvee_{x \in A, x \le k} \neg W(k - x) & \text{if it is Long Long's turn} \\
\bigvee_{x \in B, x \le k} \neg W(k - x) & \text{if it is Mao Mao's turn}
\end{cases}
$$
But turn alternates. So define two functions:
Let $ L(k) $: True if Long Long wins from state $ k $ when it is **his turn**.
Let $ M(k) $: True if Long Long wins from state $ k $ when it is **Mao Mao's turn**.
Then:
$$
L(0) = \text{False}, \quad M(0) = \text{True}
$$
For $ k \ge 1 $:
$$
L(k) = \bigvee_{\substack{x \in A \\ x \le k}} M(k - x)
$$
$$
M(k) = \bigvee_{\substack{x \in B \\ x \le k}} L(k - x)
$$
**Output**:
If $ L(n) $ is True, print "_Long Long nb!_", else print "_Mao Mao nb!_".