Uolevi and Maija are trying out a space themed strategy game - Astralis. Since this is their first time playing, they will use the simplified rule set. The game is played on a galaxy that consists of n solar systems connected by n-1 bidirectional wormholes. The i-th wormhole connects solar systems a_i and b_i. It is guaranteed that there is a path between every pair of solar systems. Before the game starts the resources have to be distributed evenly between the players. Help Uolevi and Maija by dividing the galaxy into two equally sized connected components or report that this is impossible.

Input

First line contain a single integer n.

The 𝑖-th of the next n lines contains two integers a_i and b_𝑖.

Output

Print "Yes" if the task is possible and a string of length n. The i-th character of the string is U if solar system i belongs to Uolevi and M if it belongs to Maija.

Print "No" otherwise

Constraints

• 2 \leq n \leq 10^5
• n is divisible by 2
• 1 \leq a_i < b_i \leq n
• (a_i, b_i) \neq (a_j, b_j) if i \neq j

Example 1

Input:

6
1 2
1 3
1 4
4 5
4 6

Output:

Yes
UUUMMM

Example 2

Input:

6
1 2
2 3
1 4
1 5
1 6

Output:

No