CF2147C.Rabbits

You have $n$ flower pots arranged in a line numbered from $1$ to $n$ left to right. Some of the pots contain flowers, while others are empty. You are given a binary string $s$ describing which pots contain flowers ($s_i = 1$) and which are empty ($s_i = 0$). You also have some rabbits, and you want to take a nice picture of rabbits and flowers. You want to put rabbits in every empty pot ($s_i = 0$), and for each rabbit, you can put it looking either to the left or to the right. Unfortunately, the rabbits are quite naughty, and they will try to jump, which will ruin the picture.

Each rabbit will prepare to jump into the next pot in the direction they are looking, but they won't jump if there is a rabbit in that pot already or if there is another rabbit that prepares to jump into the same pot from the opposite side. Rabbits won't jump out of the borders (a rabbit at pot $1$ looking to the left won't jump, same for a rabbit looking to the right at pot $n$).

Your goal is to choose the directions of the rabbits so that they never jump, allowing you to take your time to take the picture. You need to determine if there is a valid arrangement of rabbits such that no rabbit ever jumps.

你有 $n$ 个花盆，从左到右依次编号为 $1$ 到 $n$。其中一些花盆中种有花朵，另一些则为空。你被给定一个二进制字符串 $s$，用于描述哪些花盆中有花（$s_i = 1$）以及哪些为空（$s_i = 0$）。你还拥有一些兔子，希望拍摄一张兔子与花朵的优美合影。你需要在每一个空花盆（即满足 $s_i = 0$ 的位置）中放置一只兔子；对每只兔子，你可以让它朝左或朝右看。不幸的是，这些兔子非常调皮，它们会试图跳跃，从而破坏合影。

每只兔子将准备朝其注视的方向跳入相邻的下一个花盆；但如果目标花盆中已有一只兔子，或者有另一只兔子正从相反方向准备跳入同一花盆，则该兔子不会跳跃。此外，兔子不会跳出边界（例如，在花盆 $1$ 中朝左看的兔子不会跳跃；同理，在花盆 $n$ 中朝右看的兔子也不会跳跃）。

你的目标是为所有兔子选定朝向，使得没有任何兔子跳跃，从而让你能从容地完成拍照。你需要判断：是否存在一种兔子朝向的安排方式，使得没有任何兔子跳跃。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

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

The second line contains a binary string $s$ of size $n$, denoting the occupied and empty pots.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，表示花盆的占用与空闲状态。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print "YES" if there exists a configuration of rabbits that satisfies the condition, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果存在一种满足条件的兔子配置，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出答案（大写或小写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

Visualizer link

In the first test case, one of the valid configurations is to put a rabbit looking to the right at position $1$, a rabbit looking to the left at position $3$, and a rabbit looking to the left at position $4$. No rabbit will move since:

• The rabbit at pot $1$ won't move to pot $2$ since the rabbit at pot $3$ is looking to the left.
• The rabbit at pot $3$ won't move to pot $2$ since the rabbit at pot $1$ is looking to the right.
• The rabbit at pot $4$ won't move to pot $3$ since there is a rabbit in there.

In the second test case, one of the valid configurations is to put a rabbit looking to the left at position $1$, a rabbit looking to the right at position $2$, and a rabbit looking to the left at position $3$. No rabbit will move since:

• The rabbit at pot $1$ won't move since it is looking at the left border.
• The rabbit at pot $2$ won't move to pot $3$ since there is a rabbit in there.
• The rabbit at pot $3$ won't move to pot $2$ since there is a rabbit in there.

It can be proven that there is no valid arrangement of rabbits in the third test case.

可视化链接

在第一个测试用例中，一种合法的摆放方式为：在位置 $1$ 放置一只朝右看的兔子，在位置 $3$ 放置一只朝左看的兔子，在位置 $4$ 放置一只朝左看的兔子。此时没有任何兔子会移动，因为：

• 位于花盆 $1$ 的兔子不会移动到花盆 $2$，因为位于花盆 $3$ 的兔子朝左看；
• 位于花盆 $3$ 的兔子不会移动到花盆 $2$，因为位于花盆 $1$ 的兔子朝右看；
• 位于花盆 $4$ 的兔子不会移动到花盆 $3$，因为花盆 $3$ 中已有一只兔子。

在第二个测试用例中，一种合法的摆放方式为：在位置 $1$ 放置一只朝左看的兔子，在位置 $2$ 放置一只朝右看的兔子，在位置 $3$ 放置一只朝左看的兔子。此时没有任何兔子会移动，因为：

• 位于花盆 $1$ 的兔子不会移动，因为它正朝向左边界；
• 位于花盆 $2$ 的兔子不会移动到花盆 $3$，因为花盆 $3$ 中已有一只兔子；
• 位于花盆 $3$ 的兔子不会移动到花盆 $2$，因为花盆 $2$ 中已有一只兔子。

可以证明：第三个测试用例中不存在合法的兔子摆放方案。