Statement (easy): E0. Who can win the max leaf?

E0. Who can win the max leaf? (easy version)

This is the easy version of E. Deconstruction Tree. You do not count sets; you only decide which vertices can ever appear in $S$.

A tree with $n$ nodes fell from the sky along with an initially empty set $S$. You repeat the following $n - 1$ times:

let $x$ be the leaf with maximum index;
add $x$ into $S$ (duplicates change nothing);
delete any leaf other than $x$.

For each vertex $v$ ($1 \le v \le n$), determine whether there exists at least one valid sequence of deletions whose final set $S$ contains $v$.

Input

The same format as the full problem: $t$ test cases, each with $n$ and $n - 1$ edges of a tree ($2 \le n \le 2 \cdot 10^5$, sum of $n \le 2 \cdot 10^5$).

Output

For each test case, print a string of length $n$ over {Y, N}. The $v$-th character is Y if $v$ can appear in some achievable final set, and N otherwise.

Example

Use the same test data as the full problem. Illustrative outputs:

$n = 7$ (sample 3 in the full statement)

NNYYYYY

Vertices $1$ and $2$ never become the maximum-index leaf. Vertices $3$ through $7$ each appear in at least one of the three achievable sets $\{3, 6, 7\}$, $\{3, 4, 6, 7\}$, and $\{3, 4, 5, 6, 7\}$.

$n = 10$ (sample 4)

NNNYYYYYYY

Vertices $1$, $2$, and $3$ never win. Every vertex $4$ through $10$ appears in some outcome (for example $5$–$8$ are optional, but not impossible).

$n = 2$, edge $(1, 2)$

NY

Only vertex $2$ can be stamped into $S$.

Star centered at $5$ ($n = 5$, edges $5$–$1$, $5$–$2$, $5$–$3$, $5$–$4$)

NNNYY

There is only one distinct final set $\{4, 5\}$; vertices $1$, $2$, and $3$ never win the race.

Note

E0 is a membership problem only. You never count distinct final sets.

If you solve E0 first, you learn:

the rephrasing “$S$ = vertices that were max leaf at some round”;
the anchor $n \in S$ always;
branch champions ($\mathrm{sub}[v] < v$) versus vertices that are permanently outclassed;
a short linear feasibility sweep (see editorial_easy.md).

E1 (the full problem) reuses the same tree preprocessing but then counts distinct subsets. See editorial.md.