Quan Hệ Trên Cây

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$ và được chọn gốc tại đỉnh $1$. Một đỉnh $a$ được gọi là tổ tiên của đỉnh $b$ khi $a$ xuất hiện trên đường đi từ gốc $1$ tới $b$ và $a\ne b$.

Có $q$ truy vấn, mỗi truy vấn gồm hai đỉnh khác nhau $u$ và $v$. Với từng truy vấn, hãy xác định quan hệ của hai đỉnh theo quy tắc sau:

• In MA nếu $u$ là tổ tiên của $v$.
• Nếu điều trên không đúng, in RI nếu $v$ là tổ tiên của $u$.
• In SA nếu hai đỉnh không có quan hệ tổ tiên theo cả hai hướng.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.

• Mỗi dòng trong $n-1$ dòng tiếp theo chứa hai số nguyên $a$ và $b$, biểu diễn một cạnh vô hướng của cây.

• Mỗi dòng trong $q$ dòng cuối chứa hai số nguyên khác nhau $u$ và $v$, mô tả một truy vấn.

Output

• Với mỗi truy vấn, in trên một dòng đúng một trong ba chuỗi MA, RI, SA theo quy tắc đã nêu.

Constraints

• $1\le n,q\le 10^5$.
• $1\le a,b,u,v\le n$.
• Các cạnh tạo thành một cây và gốc của cây là đỉnh $1$.
• Trong mỗi truy vấn, $u\ne v$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

8 6
1 2
1 3
2 4
2 5
3 6
6 7
6 8
2 5
5 2
4 5
1 8
7 3
5 8

MA
RI
SA
MA
RI
SA