CF1477B Nezzar and Binary String

Nezzar 有一个长度为 $n$ 的二进制字符串 $s$，他想把它分享给他最好的朋友 Nanako。在接下来的 $q$ 天里，Nanako 会检查这个二进制字符串。同时，Nezzar 想在这 $q$ 天里把字符串 $s$ 变成字符串 $f$，因为他觉得这样更好看。 已知 Nanako 非常喜欢一致性。在第 $i$ 天，Nanako 会检查字符串 $s$ 的一个区间，从位置 $l_i$ 到 $r_i$（包含两端）。如果这个区间内同时包含字符 '0' 和 '1'，Nanako 就会不高兴并且把字符串扔掉。 在这次检查之后，在第 $i$ 天的晚上，Nezzar 可以偷偷地修改区间 $[l_i, r_i]$ 内的字符，但只能修改严格少于一半的字符，否则变化会太明显。 现在 Nezzar 想知道，是否有可能既能让 Nanako 始终保持高兴，又能在 $q$ 天后让字符串变成 $f$。

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^5$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n, q$（$1 \le n \le 2 \cdot 10^5$，$0 \le q \le 2 \cdot 10^5$）。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。 每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $f$。 接下来 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$），表示 Nanako 第 $i$ 天检查的区间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果有可能让 Nanako 始终高兴并且最终字符串变为 $f$，输出一行 "YES"。否则输出一行 "NO"。 你可以用任意大小写输出答案。

在第一个测试用例中，$\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111$ 是可能的字符串变化序列之一。 在第二个测试用例中，可以证明最终无法得到字符串 $f$。 由 ChatGPT 4.1 翻译