Description

In a country with $N$ cities, Alice wants to embark on a legendary journey. They wish to start from a city, each time moving to an adjacent city, visit exactly $K$ cities without repetition along the way, and finally arrive at another city to end the journey.

Note that the starting city and the ending city are also counted among the visited cities. That is, including the start and end, all visited cities must be distinct. Now, Alice wants to know which ordered city pairs $(u, v)$ can serve as a valid start and end for such a journey.

Input Format

Each test file contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains three integers $N$, $M$, and $K$, denoting the number of cities, the number of adjacency relations between cities, and the number of cities that the trip should visit.

The next $M$ lines each contain two integers $u$ and $v$, indicating that city $u$ and city $v$ are adjacent, i.e., you can travel from either city to the other.

$N\le 1000$, $M\le 5000$, $2\le K\le 7$, and $T\times \left\lfloor \frac k 2 \right\rfloor^{\left\lfloor \frac k 2 \right\rfloor}\le 60$.

Output Format

For each test case, output $N$ lines, each containing $N$ characters. In the $i$-th row, the $j$-th character is either Y or N, indicating whether there exists a valid travel plan starting from city $i$ and ending at city $j$.

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

NYYYY 
YNNYY 
YNNYN 
YYYNY 
YYNYN

Hint

2024-11-15: Added hack testdata.

Translated by ChatGPT 5