34491번 - Monster Fighting 서브태스크다국어

문제

Busy Beaver is playing his favorite adventure game, where he battles wild monsters with monsters of his own!

In this game, there are two types of monsters: light and dark. Each monster has exactly one type, and some positive integer power level. A monster with power $p$ can defeat another monster $q$ if either $p \geq q,ドル or if they have the same type and 2ドルp \geq q$.

Busy Beaver has just encountered $N$ monsters, and he also has $N$ monsters in his party. To defend against the encounter, he needs to pair his monsters with the opposing monsters such that in each pair, Busy Beaver's monster can defeat the opposing monster according to the rules above. Given the types and power levels of each of the monsters, please report whether or not such a pairing exists.

입력

Each test contains multiple test cases. The first line of input contains a single integer $T$ $(1 \leq T \leq 10^5),ドル the number of test cases. The description of each test case follows.

The first line of each test case contains a single positive integer $N$ (1ドル \leq N \leq 2 \cdot 10^5$).

Then, $N$ lines of input follow, describing Busy Beaver's monsters. The $i$th line contains two positive integers $p_i, s_i$ (1ドル \leq p_i \leq 10^9, s_i \in \{0, 1\}$) --- the power level $p_i$ and type $s_i$ of the $i$th monster. $s_i = 0$ denotes a light-type monster, and $s_i = 1$ denotes a dark-type monster.

After that, there are $N$ more lines of input, describing the encountered monsters. The $i$th line contains two positive integers $q_i, t_i$ (1ドル \leq q_i \leq 10^9, t_i \in \{0, 1\}$) --- the power level $q_i$ and type $t_i$ of the $i$th monster. $t_i = 0$ denotes a light-type monster, and $t_i = 1$ denotes a dark-type monster.

It is guaranteed that the sum of $N$ across all test cases is no more than 2ドル \cdot 10^5$.

출력

For each test case, output "YES" (without quotes) if a desired pairing exists, and "NO" (without quotes) otherwise.

제한

서브태스크

노트

In the sample input, there are two test cases. For the first case, we can construct a pairing as follows:

• Your light type monster of power level 2ドル$ can defeat the identical opposing monster.
• Your light type monster of power level 3ドル$ can defeat the identical opposing monster.
• Your first dark type monster of power level 1ドル$ can defeat the opposing dark type monster of power level 2ドル$.
• Your second dark type monster of power level 1ドル$ can defeat the opposing light type monster of power level 1ドル$.

In the second case, it can be shown that no pairing exists.