시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB1122100.000%

문제

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 $2p \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.

서브태스크

번호배점제한
130

The sum of $N$ across all test cases does not exceed $2 \cdot 10^3$.

270

No additional constraints.

예제 입력 1

2
4
2 0
3 0
1 1
1 1
1 0
2 0
3 0
2 1
2
1 1
5 1
1 0
1000000000 0

예제 출력 1

YES
NO

노트

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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.