Given a tree with $n$ vertices rooted at $1$. There are $q$ queries, each consisting of two vertices $u$ and $v$. Determine whether $u$ is an ancestor of $v$, $v$ is an ancestor of $u$, or neither.
Define ancestor: Let $p_i$ be the immediate parent of $i$ in the tree. We have $p_u$ as the ancestor of $u$, $p_{p_u}$ as the ancestor of $u$, $p_{p_{p_u}}$ as the ancestor of $u$, and so on. In other words, the parent of $u$ is the ancestor of $u$, the parent of the parent of $u$ is the ancestor of $u$, and so on.
### Input
- The first line contains two integers $n$ and $q$.
- The next $n-1$ lines each contain two integers $u$ and $v$, indicating there is an edge between $u$ and $v$.
- The next $q$ lines each contain two integers $u$ and $v$, representing a query. Ensure $u \neq v$.
### Output
- For each query, print:
+ `MA` if $u$ is an ancestor of $v$.
+ `RI` if $v$ is an ancestor of $u$.
+ `SA` otherwise.
### Constraints
- $1 \le n,q \le 10^5$.
- $1 \le u, v \le n$.
### Example
Input:
```
6 6
3 4
4 5
5 6
3 2
5 1
5 6
4 3
6 2
5 1
3 5
6 4
```
Output:
```
MA
MA
SA
RI
RI
SA
```
