Soldiers (Small)

Time limit5sMemory limit512 MB

Summary

Two players alternately pick soldiers whose attack or defense beats everything picked so far; decide if the first player can guarantee ending with more picks.

Level: Medium7 of 10
Topics: Game theory, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

General Alice and General Bob play a war game with $N$ soldiers. Soldier $i$ has an attack value $A_i$ and a defense value $D_i$ .

Before the game starts, the two generals take turns selecting soldiers, and Alice selects first. Let $S$ be the set of soldiers selected so far. On a turn, a player may select soldier $x$ if at least one of these two conditions holds:

$A_x > A_s$ for every soldier $s$ in $S$
$D_x > D_s$ for every soldier $s$ in $S$

While $S$ is empty both conditions hold, so the first selection may be any soldier. A soldier already in $S$ can never be selected again, because it does not beat its own attack or its own defense. When the player to move has no legal selection, the selection process ends and the game starts.

Alice wants to finish with more soldiers than Bob, and Bob wants to stop her. Both generals play optimally toward their own goal. Decide whether Alice succeeds.

Input

The first line contains the number of test cases $T$ . Each test case begins with a line holding $N$ , the number of soldiers. The next $N$ lines each hold two integers $A_i$ and $D_i$ , the attack and defense values of the $i$ -th soldier.

Constraints:

$1 \le T \le 10$
$1 \le N \le 200$
$1 \le A_i, D_i \le 10000$

Output

For each test case, print one line in the form Case #x: y. Here x is the test case number starting from 1, and y is YES if Alice can guarantee that she selects more soldiers than Bob no matter how Bob plays, and NO otherwise.

Examples2

Example 1

Input

Expected output

Case #1: NO
Case #2: YES
Case #3: YES

Example 2
Input
```
1
1
7 9
```
Expected output
```
Case #1: YES
```