Viaggio intrigante

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: quadrante.c
• Scarica la traccia in C++: quadrante.cpp
• Scarica la traccia in Python: quadrante.py
• Scarica la traccia in Java: quadrante.java
• Scarica la traccia in C#: quadrante.cs
• Scarica la traccia in JavaScript: quadrante.html
• Scarica la traccia in Rust: quadrante.rs

Descrizione del problema

Davide sta organizzando un viaggio su una griglia infinita, muovendosi solo verso l'alto e verso destra.

Davide parte dal punto $(0,\, 0)$ e vorrebbe visitare $N$ città, numerate da $0$ a $N-1$ nell'ordine di quanto Davide le trova interessanti, che si trovano rispettivamente nei punti $(x_i,\, y_i)$, cioè sulla $x_i$-esima colonna e sulla $y_i$-esima riga. Rendendosi presto conto che potrebbe non essere in grado di visitarle tutte (muovendosi solo in alto o a destra), Davide decide di considerare anche degli itinerari ridotti. Un prefisso delle città è, fissato un intero $0 \le p < N$, l'insieme delle città con indice minore o uguale a $p$: in altre parole, le $p+1$ città più interessanti per Davide. Aiuta Davide a capire quanti prefissi sono completamente visitabili!

Un prefisso è completamente visitabile se, partendo da $(0,\, 0)$ e muovendosi solo verso l'alto e verso destra, Davide riesce a visitare tutte le città in esso, in un qualsiasi ordine.

Esempi

Come primo esempio, consideriamo che le uniche due città interessanti per Davide siano (in ordine) nelle posizioni $(1,\, 2)$ e $(2,\, 1)$. In questo caso la risposta è 1, infatti:

• Il prefisso che contiene solo la città in $(1,\, 2)$ è completamente visitabile;
• Il prefisso che contiene entrambe le città non è completamente visitabile: da qualunque delle due venga visitata per prima non si riesce a raggiungere l'altra.

Come secondo esempio, consideriamo che le 4 città interessanti per Davide siano (in ordine) nelle posizioni $(3,\, 4)$, $(1,\, 3)$, $(2,\, 3)$ e $(2,\, 1)$. In questo caso la risposta è 3, infatti:

• Il prefisso che contiene solo la città in $(3,\, 4)$ è completamente visitabile;
• Il prefisso che contiene le prime due città è completamente visitabile spostandosi solo verso l'alto e verso destra, come mostrato nella prima figura sotto;
• Il prefisso che contiene le prime tre città è completamente visitabile, come mostrato nella seconda figura;
• Il prefisso che contiene tutte le città mostrato nella terza figura non è completamente visitabile.

Assunzioni

• $T = 10$, nei file di input che scaricherai saranno presenti esattamente $10$ casi di test.
• $1 \le N \le 10^5$
• $0 \le x_i,y_i \le 10^9$, per ogni $0 \le i < N$

Nei primi $2$ casi di test vale $N \le 100$. Nei primi $4$ casi di test vale $N \le 1000$.

Formato di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• la prima riga contiene un intero $N$, il numero di città.
• le $N$ righe seguenti contengono $2$ interi ciascuna, le coordinate $(x_i, y_i)$ dell' $i$-esima città.

Formato di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: p

dove t è il numero del caso di test (a partire da $1$) e il valore p è il numero di prefissi completamente visitabili.

Esempi di input/output

Gli esempi descritti sopra si rappresentano nel formato di input/output nel seguente modo.

---

Input:

2

2
1 2
2 1

4
3 4
1 3
2 3
2 1

---

Output:

Case #1: 1
Case #2: 3

---