409961: GYM103870 F Cloning

Misaka is confused. She is staring at her front yard, a garden of length $$$N$$$, and it seems to be lined with trees... and her clones? As Misaka looks at her front yard, she notices that for certain segments of her front yard there are an equal amount of clones and trees. Her memory has gotten worse so she has forgotten what her front yard looked like on that day. However, she still remembers $$$M$$$ intervals where the number of clones and trees were the same. Misaka wants you to find any possible arrangement of clones and trees such that it matches with the intervals she remembers.

The first line contains an integer $$$T$$$, denoting the number of testcases $$$(1 \leq T \leq 10)$$$.

Each test case starts off with one line containing two integers $$$n, m$$$, the length of her front yard and the number of segments she remembers. $$$(1 \leq n \leq 100, 1 \leq m \leq 1000)$$$.

The following $$$m$$$ lines containing two integers each $$$l,r$$$, $$$(1 \leq l \leq r \leq n)$$$ denoting that the segment $$$[l \cdots r]$$$ had the same number of clones as trees.

It is guaranteed the sum of $$$n$$$ over all test cases is not greater than $$$100$$$ and the sum of $$$m$$$ over all test cases is not greater than $$$1000$$$.

For each test case, if there is a solution, output "Y" on one line, then output a string length $$$n$$$ of "M"'s and "T"'s where an "M" denotes a clone and "T" denotes a tree on the next line. For the string outputted, it must satisfy every one of the $$$m$$$ constraints specified in the input. If there are multiple solutions, output any.

If there is no solution, then just output "N" on its own line.

2
5 3
1 4
4 5
2 3
5 1
1 5

Y
MMTTM
N

—

Idea: 3366

Preparation: 3366

Occurrences: Novice 6, Intermediate 5