#CF1948C. 箭头路径

    ID: 6575 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>搜索枚举DFS其他构造动态规划图结构最短路*1300

箭头路径

C. 箭头路径

单个测试点时间限制22单个测试点内存限制256256 兆字节

有一个 22nn 列的网格。行从上到下编号为 1122,列从左到右编号为 11nn。网格的每个格子里有一个箭头,指向。保证没有箭头会指向网格外。

有一个机器人从格子 (1,1)(1,1) 出发。每一秒会依次发生以下两个动作:

  1. 机器人先向上、下、左、右中某一方向移动一步(不能出界,也不能不动)。
  2. 然后,机器人沿着当前所在格子里的箭头方向再移动一步。

你需要判断机器人是否能够到达格子 (2,n)(2,n)


输入格式

第一行一个整数 tt1t1041\le t\le 10^4)—— 测试用例数量。

每个测试用例:

  • 第一行一个整数 nn2n21052\le n\le 2\cdot 10^5)。
  • 第二行一个长度为 nn 的字符串,仅包含 <>,表示网格第一行的箭头。
  • 第三行一个长度为 nn 的字符串,仅包含 <>,表示网格第二行的箭头。

额外保证:

  • nn 是偶数;
  • 没有箭头指向网格外;
  • 所有测试用例的 nn 之和不超过 21052\cdot 10^5

输出格式

对于每个测试用例,如果可以到达 (2,n)(2,n),输出 YES,否则输出 NO


样例输入

4
4
>><<
>>><
2
><
><
4
>>><
>><<
6
>><<><
><>>><

样例输出

YES
YES
NO
YES