Scheduling Tasks on Two Machines

You are given a set of tasks. Each task is defined by its start time and end time. The objective is to schedule all tasks on at most two machines such that no two tasks overlap on the same machine.

A task i is represented by its start time \(s_i\) and end time \(e_i\). Two tasks can be scheduled on the same machine if the start time of one is not less than the end time of the other, i.e. for tasks \(i\) and \(j\), they do not conflict if \(s_j \ge e_i\).

Your goal is to determine the minimum number of machines required (either 1 or 2) to schedule all tasks. If the tasks cannot be scheduled on two machines, output \(-1\).

Note: Even if it is possible to schedule all tasks on one machine, you must determine the minimum number needed. In other words, if one machine is sufficient then answer is 1; if two machines are required then answer is 2; if scheduling is impossible with two machines then answer is -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n₁
s₁ e₁
s₂ e₂
... 
sₙ₁ eₙ₁
n₂
s₁ e₁
s₂ e₂
... 
...

Here, the first line contains an integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(n\) (the number of tasks). The next \(n\) lines each contain two integers \(s\) and \(e\) (the start and end times of a task).

outputFormat

For each test case, print a single line containing the minimum number of machines required to schedule all tasks without overlap on the same machine. If the tasks cannot be scheduled on two machines, print \(-1\).

## sample

3
3
1 3
2 5
4 6
2
1 2
2 3
4
1 2
2 3
3 4
4 5

2
1
1

</p>