I、Interesting Computer Game

给出T组数据，每组数据都是一个对数N在第一行，紧接N行每行都是一对二元组。N<1e5
现在你可以在每对二元组之间选一个数出来，但是这个数之前一定不能被选过。问你能选的最多二元组对数是多少？
最多只有1e5组数据，但是数据大小是1e9，第一就是离散做法。
而且通过赛后补题发现这种类型的题目都可以通过并查集解决，每日一题也有一题类似的。8月14日
我们把全部数据读入完成后进行离散操作。
紧接着我们对每对二元组之间加个vis标记代表是否形成了自身闭环，与sz数组代表每个根节点的连通块大小。
那么我们是寻找最多能选择的二元组，每次进行find找根操作，如果是同一个根，说明形成了闭环，吧闭环打上vis标记。
如果不是一个根，连接这两个连通块大小，并且吧vis也一起合并过去。
最后遍历全部节点，如果这个连通块不存在闭环，只能选择sz[i]-1个数。如果存在一个或者多个闭环都可以选上这个连通块中全部拥有的节点数。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 2e5 + 7;

int fa[N], sz[N], vis[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int l[N], r[N];
vector<int> p;
int id(int x) {
    return lower_bound(all(p), x) - p.begin() + 1;
}

int main() {
    int T = read();
    for (int ca = 1; ca <= T; ++ca) {
        p.clear();
        int n = read();
        for (int i = 1; i <= n << 1; ++i)
            fa[i] = i, vis[i] = 0, sz[i] = 1;

        for (int i = 1; i <= n; ++i) {
            l[i] = read(), r[i] = read();
            p.push_back(l[i]);
            p.push_back(r[i]);
        }
        sort(all(p));
        p.erase(unique(all(p)), p.end());
        int m = p.size();

        for (int i = 1; i <= n; ++i) {
            int a = id(l[i]), b = id(r[i]);
            int fx = find(a), fy = find(b);
            if (fx != fy) {
                fa[fy] = fx;
                vis[fx] |= vis[fy];
                sz[fx] += sz[fy];
            }
            else vis[fx] = 1;
        }
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            int fi = find(i);
            if (vis[fi])    ++ans, vis[fi] = 0;
            if (fi == i)    ans += sz[fi] - 1;
        }

        printf("Case #%d: %d\n", ca, ans);
    }
    return 0;
}