Nezzar and Binary String

题意翻译

A 有一个长度为 $n$ 的二进制串 S，他想让自己最好的朋友 B 看，B将会用 $q$ 天的时间来检查这个二进制串。 第 $i$ 天， B会在这一天早上检查这个二进制串的一个区间 $[l_i,r_i]$ ，如果这个区间内的数字全部都是一致的，也就是全部都为 $1$ 或者全部都为 $0$ ，B就会很开心，否则她就会不开心。 A为了使 B 每次检查都能变得开心，所以 A 会在每天 B 检查之后的当天晚上偷偷地去修改这个二进制串，使得 B 第二天检查的时候能够开心。为了不被 B 发现，A 每次只能修改今天早上 B 检查过的那个区间 $[l_i,r_i]$，并且修改的字符的个数必须**小于**这个区间字符总数的一半， 与此同时，A还有一个任务，就是他希望可以通过这 $q$ 天的修改，将二进制串 $s$ 变成 $f$ 。请问 A 能够在每天都保证 B 开心的同时，将二进制串 $s$ 修改为 $f$ 呢吗？ $T$ 组数据，每组输入两个整数 $n$ 和 $q$ ，然后输入两个二进制串 $s$ 和 $f$，接着输入 $q$ 个区间。若 A 能在保证 B 每次都开心的前提下，完成这个任务，则输出 `YES` 否则输出 `NO`。 $1 \le t \le 2 \cdot 10^5,1 \le n \le 2 \cdot 10^5,0 \le q \le 2 \cdot 10^5$

题目描述

Nezzar has a binary string $ s $ of length $ n $ that he wants to share with his best friend, Nanako. Nanako will spend $ q $ days inspecting the binary string. At the same time, Nezzar wants to change the string $ s $ into string $ f $ during these $ q $ days, because it looks better. It is known that Nanako loves consistency so much. On the $ i $ -th day, Nanako will inspect a segment of string $ s $ from position $ l_i $ to position $ r_i $ inclusive. If the segment contains both characters '0' and '1', Nanako becomes unhappy and throws away the string. After this inspection, at the $ i $ -th night, Nezzar can secretly change strictly less than half of the characters in the segment from $ l_i $ to $ r_i $ inclusive, otherwise the change will be too obvious. Now Nezzar wonders, if it is possible to avoid Nanako being unhappy and at the same time have the string become equal to the string $ f $ at the end of these $ q $ days and nights.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^5 $ ) — the number of test cases. The first line of each test case contains two integers $ n,q $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 0 \le q \le 2 \cdot 10^5 $ ). The second line of each test case contains a binary string $ s $ of length $ n $ . The third line of each test case contains a binary string $ f $ of length $ n $ . Then $ q $ lines follow, $ i $ -th of them contains two integers $ l_i,r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — bounds of the segment, that Nanako will inspect on the $ i $ -th day. It is guaranteed that the sum of $ n $ for all test cases doesn't exceed $ 2 \cdot 10^5 $ , and the sum of $ q $ for all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print "YES" on the single line if it is possible to avoid Nanako being unhappy and have the string $ f $ at the end of $ q $ days and nights. Otherwise, print "NO". You can print each letter in any case (upper or lower).

输入输出样例

输入样例 #1

4
5 2
00000
00111
1 5
1 3
2 1
00
01
1 2
10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10
5 2
10000
11000
2 5
1 3

输出样例 #1

YES
NO
YES
NO

说明

In the first test case, $ \underline{00000} \rightarrow \underline{000}11 \rightarrow 00111 $ is one of the possible sequences of string changes. In the second test case, it can be shown that it is impossible to have the string $ f $ at the end.