SP28459 TAP2016E - Grumpy uncle

[由于SPOJ限制，此问题已相对于2016年阿根廷编程锦标赛中使用的原始版本进行了修改，以便每个输入文件都有多个测试用例。 ] 恩洛戈尼亚的冬天很艰难，所以厄尼叔叔决定今年买一个加热器来保暖。虽然这非常困难，但他还是设法听从了朋友的建议，买了一个可以通过智能手机控制的智能加热器。然而，厄尼叔叔并不完全理解他的智能手机，所以他很难找到用于设置加热器温度的应用程序。 厄尼叔叔在他的智能手机上安装了 $N$ 个从 $1$ 到 $N$ 的应用程序，对应于控制加热器的应用程序的数字 $1$ 。他的智能手机有 $M$ 个按钮，从 $1$ 到 $M$ 编号，用于从一个应用程序切换到另一个。更具体地说，如果智能手机当前打开了应用程序编号 $i$ ，厄尼叔叔按下了按钮编号 $j$ ，则应用程序 $i$ 关闭，然后应用程序 $T_{i,j}$ 打开。问题是厄尼叔叔无法区分不同的应用程序，所以他永远不知道自己是否打开了正确的应用程序。 厄尼叔叔脾气很暴躁，所以你决定帮助他，以避免每次加热器的温度不太适合他时都要听他的抱怨。你的任务是向他提供一个按钮列表，他可以将其用作指令，这样如果他按列表中按钮出现的顺序按下，他的手机就会打开控制加热器的应用程序。因为你不想给他提供多个列表，所以你应该创建一个如上所述的列表，与厄尼叔叔开始执行指令时打开的应用程序无关。 例如，手机有 $N=3$ 个应用程序和 $M=2$ 个按钮，即： $ T_{1,1}=T_{2,1}=T_{3,1}=T_{1,2}=2$ $ T_{2,2}=T_{3,2}=1$ 在这种情况下，可以提供给厄尼叔叔的按钮序列将是 { $1,2$ } ，因为会发生以下情况之一： - 如果厄尼叔叔在应用程序 $1$ 打开的情况下开始，按下按钮 $1$ 会让他打开应用程序 $3$ ；则按下按钮 $2$ 将导致应用程序1再次打开的最终状态。 - 另一方面，如果厄尼叔叔在应用程序2打开的情况下启动，按下按钮 $1$ 会让他打开应用程序 $3$ ；则按下按钮 $2$ 将导致应用程序 $1$ 打开的最终状态。 - 最后，如果他开始时应用程序 $3$ 是打开的，按下按钮 $1$ 会让他看到应用程序 $2$ 是打开的；则按下按钮 $2$ 将返回到应用程序 $1$ 打开的最终状态。 因此，无论在按钮按下序列开始时打开了哪个应用程序，厄尼叔叔总是会在序列结束时到达应用程序 $1$ 。 现在，有时不可能找到厄尼叔叔可以按下的一系列按钮，这样当他完成操作时，打开的应用程序总是应用程序编号 $1$ 。例如，在 $N=3$ 和 $M=2$ 的情况下，如果我们有： $T_{1,1}=T_{2,2}=3$ 和 $T_{3,1}=T_{3,2}=1$ 在任何按钮按下序列结束时打开的应用程序始终取决于序列启动时打开的是哪个应用程序。因此，在这种情况下，不可能找到一个总是让厄尼叔叔的手机打开应用程序 $1$ 的序列。 为了不浪费时间寻找不存在的按钮按下序列，您想先找出是否有可能通过找到上述序列来满足厄尼叔叔的要求。如果是这样，厄尼叔叔会很高兴知道他可以随时打开他最喜欢的2级加热器……因此，我们将永远心存感激。

输入文件中有多个测试用例。第一行包含两个整数 $N$ 和 $M$ ，分别表示厄尼叔叔智能手机中的应用程序数量和按钮数量： $1 \leqslant N,M $ 且 $1 \leqslant NM \leqslant 10^4$ 。 以下 $N$ 行中的每一行都包含 $M$ 个整数，即第 $i$ 行 $T$ 中的第 $j$ 个数字，表示在应用程序编号 $i$ 打开时按下按钮 $j$ 打开的应用程序： 对于 $ i=1 , 2 , ... , N$ 和 $ j=1 , 2 , ... , M$ 。 $ 1 \leqslant T_{i,j} \leqslant N$

对于每个测试用例，输出一个字符，表示是否可以找到问题陈述中描述的按钮序列。如果可以找到序列，则字符应为“S”，否则为“N”。