DSU2

In Uzhlandia, there are ( n ) cities numbered from 1 to ( n ). Currently, there are no roads, but over time, roads will be constructed. Additionally, Uzhlandia plans to build premium roads, which have better asphalt and traffic conditions, but require a toll. Tourist Vasyl has asked you to handle ( q ) queries of three types:

1. 1 a b - Establish a two-way road between cities ( a ) and ( b ).

2. 2 a b - Establish a two-way premium road between cities ( a ) and ( b ).

3. 3 a b - Determine if it is possible to travel from city ( a ) to city ( b ) using only premium roads. If so, output "$$$". If travel is possible using any roads, output "YES". If travel is not possible at all, output "NO".

Input

The first line contains the integers ( n ) and ( q ) (1 ≤ ( n, q ) ≤ 3 \times 10^5).The following ( q ) lines contain the queries.

Output

Provide the answers to the queries of type 3.

Examples