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

The first line contains a single integer n.

The i-th of the next n lines contains two integers a_i and b_i.

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