{"raw_statement":[{"iden":"statement","content":"Ayutthaya was one of the first kingdoms in Thailand, spanning since its foundation in 1350 to its collapse in 1767. The organization of Extraordinary Mystery Investigators (IME, in their language) aims to uncover the secrets of this ancient kingdom. One of IME's most notorious historians is Márcio \"the indispensable\" Himura. He is currently researching the laws and punishments in place during King Ramathibodi I's rule. Recent discoveries suggest how Ramathibodi I used to punish the subjects that did not convert to Theravada Buddhism, the religion he adopted.\n\nThe punishment involved trapping the accused prisoner in a room with a single exit and to light up a fire. If the prisoner could manage to reach the exit before getting caught on fire, she or he was forgiven and allowed to live. Márcio has access to some records that describe the floorplans of the rooms where this punishment took place. However, there are no documents asserting whether the prisoners were forgiven. Márcio would like to know whether each of these prisoners had any chance at all of having been forgiven. For that, Márcio represented each room as a grid with N rows and M columns, where each position has a symbol with the following meaning\n\nwhere \"start\" is the person's initial position in the room when fire has been lit up. Moreover, Márcio imposed the following constraints in his model: \n\nYou are a member of IME and Márcio would like to know if you deserve your position. He has charged you with the task of determining whether a prisoner had any chance to be forgiven.\n\nThe first line has a single integer T, the number if test cases.\n\nEach instance consists of several lines. The first line contains two integers, N and M. Each of the following N lines contains exactly M symbols representing, as described above, a room from which the prisoner must escape.\n\n*Limits* \n\nFor each instance, print a single line containing a single character. Print _Y_ if the prisoner had any chance of being forgiven; otherwise, print _N_.\n\n"},{"iden":"input","content":"The first line has a single integer T, the number if test cases.Each instance consists of several lines. The first line contains two integers, N and M. Each of the following N lines contains exactly M symbols representing, as described above, a room from which the prisoner must escape.*Limits*   1 ≤ T ≤ 100  The sum of the sizes of the matrices in all test cases will not exceed 2·106  1 ≤ N ≤ 103  1 ≤ M ≤ 103 "},{"iden":"output","content":"For each instance, print a single line containing a single character. Print _Y_ if the prisoner had any chance of being forgiven; otherwise, print _N_."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ N, M \\in \\mathbb{Z} $ denote the dimensions of a grid.  \nLet $ G \\in \\{\\texttt{.}, \\texttt{\\#}, \\texttt{S}, \\texttt{F}\\}^{N \\times M} $ be a grid where:  \n- $ \\texttt{.} $: free space  \n- $ \\texttt{\\#} $: wall (impassable)  \n- $ \\texttt{S} $: start position (exactly one)  \n- $ \\texttt{F} $: fire source (exactly one)  \n- Exit: any boundary cell that is not a wall (i.e., $ \\texttt{.} $ or $ \\texttt{S} $)  \n\nLet $ s = (r_s, c_s) \\in \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the start position.  \nLet $ f = (r_f, c_f) \\in \\{1, \\dots, N\\} \\times \\{1, \\dots, M\\} $ be the fire source.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ 2 \\le N, M \\le 100 $  \n3. Grid contains exactly one $ \\texttt{S} $ and one $ \\texttt{F} $.  \n4. Movement: prisoner and fire spread in 4 directions (up, down, left, right) per time step.  \n5. Fire spreads simultaneously in all 4 directions from all current fire cells at each time step.  \n6. Prisoner moves first, then fire spreads.  \n7. Prisoner escapes if reaching any boundary cell (edge of grid) before fire reaches that cell.  \n8. Fire and prisoner cannot occupy the same cell at the same time.  \n9. Fire does not spread through walls.  \n\n**Objective**  \nFor each test case, determine if there exists a path from $ s $ to any boundary cell (not blocked by wall) such that the prisoner reaches it in strictly fewer steps than the fire.  \nOutput:  \n- $ \\texttt{Y} $ if such a path exists  \n- $ \\texttt{N} $ otherwise","simple_statement":"Given a grid with start point, fire, walls, and empty spaces, fire spreads in 4 directions each second. The prisoner can move in 4 directions each second. Can the prisoner reach the exit before the fire catches them? Print 'Y' if possible, 'N' otherwise.","has_page_source":false}