UVa 10020 - Minimal coverage

// UVa 10020 - Minimal coverage

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct pa {
	int l, r;
};

bool operator <(pa a, pa b) {
	return a.l < b.l || (a.l == b.l && a.r > b.r);
}

int main() {

	int cases;
	for (cin >> cases; cases; cases--) {
		int m;
		cin >> m;
		vector<pa> v;
		long int l, r;
		cin >> l >> r;
		while (l || r) {
			if (l < m && r > 0) {
				pa p = { l, r };
				v.push_back(p);
			}
			cin >> l >> r;
		}
		sort(v.begin(), v.end());

		vector<pa> sol;
		vector<pa>::const_iterator I = v.begin();
		int upto = 0;
		if (v.size() > 0) {
			pa sl;
			while (upto < m) {
				int mx = upto;
				while (I != v.end() && I->l <= upto) {
					if (I->r > mx) {
						mx = I->r;
						sl = *I;
					}
					I++;
				}
				if (upto == mx)
					break;
				sol.push_back(sl);
				upto = mx;
			}
		}
		if (upto < m)
			cout << 0 << endl;
		else {
			cout << sol.size() << endl;
			for (int i = 0; i < sol.size(); i++)
				cout << sol[i].l << " " << sol[i].r << endl;
		}
		if (cases)
			cout << endl;
	}

	return 0;
}