Məsələlər
Division
Division
Две горнодобывающие компании совместно нашли хорошее место для добычи золота. Теперь начались жесткие переговоры: земельный участок должен быть разделен между компаниями.
Территория имеет форму квадрата и разделена на \textbf{n} * \textbf{n} единичных квадратов. Каждый малый квадрат либо пустой, либо содержит один или два месторождения золота. Вам следует разбить местность на две связные области, не обязательно одинаковых либо имеющих одинаковую площадь.
Компаниям будет лучше, если будут учтены следующие простые предложения. Граница между их областями должна начинаться в северо-западном углу, а заканчиваться в юго-восточном, а идти должна по границам единичных квадратов. Длина границы не должна превышать \textbf{2n}. Каждая из двух частей должна содержать одинаковое количество месторождений золота.
\InputFile
The first line contains the number of test cases \textbf{t}. The test cases follow.
The first line of a test case contains a single integer \textbf{n}, the length of the side of the plot (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}). The next \textbf{n} lines contain the description of the plot: \textbf{n} rows containing \textbf{n} integers each. These are the numbers of gold deposits in the unit squares, equal to either \textbf{0}, \textbf{1} or \textbf{2}. The first row is the northernmost one, and every row is printed from its western end to the eastern one.
\OutputFile
For each test case, output:
\begin{itemize}
\item either a single word \textbf{IMPOSSIBLE}, if there is no viable proposition of the land division,
\item or the description of the border, if a suitable proposition exists. Print a sequence of at most \textbf{2n} letters \textbf{N}, \textbf{E}, \textbf{S} or \textbf{W}, describing the border from the northwest to the southeast corner. The letters mean that the border goes north, east, south or west, respectively.
\end{itemize}
If there are multiple solutions, output any one of them.
Giriş verilənləri #1
1 5 2 0 1 0 2 0 0 2 0 0 0 0 2 1 0 1 1 0 0 0 0 2 0 0 0
Çıxış verilənləri #1
SEESEESESS