H. HNOI2010
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This problem is an enhanced edition of the "Planar" problem from the HNOI2010.

You are given $$$n$$$ pairs of numbers, where the i-th pair is $$$(x_i,y_i)$$$.

Construct a undirected graph according to the following method:

$$$\forall i,j\in [1,n]$$$, there is an edge between node $$$i$$$ and node $$$j$$$ if and only if either $$$x_i \lt x_j \lt y_i \lt y_j$$$ or $$$x_j \lt x_i \lt y_j \lt y_i$$$.

Determine if this graph is a bipartite graph.

A graph is bipartite if and only if it does not contain an odd cycle.

Input

Each test consists of multiple test cases. The initial line presents a single integer $$$T~(1\le T\le 10^5)$$$ , which denotes the quantity of test cases

In the context of each test instance, the initial line presents a single integer $$$n~(1\le n,\sum n\le 5 \cdot 10^5)$$$, representing the quantity of pairs to be evaluated. Subsequently, $$$n$$$ lines follow, with each delineating the specifics of a distinct pair. On the i-th line, a pair of integers $$$x_i,~y_i~(1\le x_i\le y_i \le 10^{18})$$$ is provided.

Output

If the graph is bipartite, print "YES". Otherwise, print "NO".

Example
Input
2
3
1 4
2 5
3 6
3
1 2
3 4
5 6
Output
NO
YES