Arrow Path
Contest: Educational Codeforces Round 163 (Rated for Div. 2)
Difficulty rating: 1300
Tags: brute force, constructive algorithms, dfs and similar, dp, graphs, shortest paths

There is a grid, consisting of $$$2$$$ rows and $$$n$$$ columns. The rows are numbered from $$$1$$$ to $$$2$$$ from top to bottom. The columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell of the grid contains an arrow pointing either to the left or to the right. No arrow points outside the grid.

There is a robot that starts in a cell $$$(1, 1)$$$. Every second, the following two actions happen one after another:

1. Firstly, the robot moves left, right, down or up (it can't try to go outside the grid, and can't skip a move);
2. then it moves along the arrow that is placed in the current cell (the cell it ends up after its move).

Your task is to determine whether the robot can reach the cell $$$(2, n)$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains a string consisting of exactly $$$n$$$ characters < and/or > — the first row of the grid.

The third line contains a string consisting of exactly $$$n$$$ characters < and/or > — the second row of the grid.

Additional constraints on the input:

- $$$n$$$ is even;
- there are no arrows pointing outside the grid;
- the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print YES if the robot can reach the cell $$$(2, n)$$$; otherwise, print NO.

You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as positive answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$$$.

In the second example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$.

In the third example, there is no way to reach the cell $$$(2, 4)$$$.

In the fourth example, one of the possible paths looks as follows: $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (2, 5) \rightarrow (2, 6)$$$.

Example input:
4
4
>><<
>>><
2
><
><
4
>>><
>><<
6
>><<><
><>>><

Example output:
YES
YES
NO
YES

Editorial:
There are multiple different approaches to this problem. We will describe a couple of them.
The key observation for this problem that works for all these approaches is that, since we never skip a move and never try to move outside the grid, we can split the cells into two groups:
• if the sum of coordinates of the cell is even (we will call it "even cell"), we can end up in such a cell only after moving along the arrow (only after the second action during each second);
• otherwise, if the sum of coordinates of the cell is odd (we will call it "odd cell"), we can end up in such a cell only after making a move on our own (only after the first action during each second).
Each movement leads us from one of these groups to the other group, that's why we always visit even cells after the second action and odd cells after the first action during each second.
Solution 1 (graph-based). Create a graph where each cell is represented by a vertex; if this is an even cell, then the robot can choose any direction from it, so we add directed arcs from it into all adjacent cells. If this is an odd cell, then the robot will be forced to move along the arrow in that cell, so we add only one directed arc from the corresponding vertex. Then we check if the vertex representing $$$(2, n)$$$ is reachable from the vertex representing $$$(1, 1)$$$ via DFS or BFS.
Solution 2 (observation-based). We can try searching for a pattern that "blocks" our robot, i. e. does not let it advance further. If there are two adjacent by angle odd cells, which both have arrows leading to the left, then every path of the robot will pass through at least one of them; and every time it goes through one of them, it will be forced to the left. So any pair of odd <-type cells which share an angle (i. e. are on the same diagonal) means that the answer is NO. Otherwise, we can show that the answer is yes; the proof is based on the fact that for every even cell, either the cell in the same column or the cell to the right will contain an arrow leading to the right, so we can always go forward.