C++11(clang++ 3.9) 解法, 执行用时: 150ms, 内存消耗: 1380K, 提交时间: 2018-03-29 11:27:37

#include <cstdio> 
#include <iostream> 
#include <cmath> 
#include <string> 
#include <list> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <utility> 
#include <set> 
#include <map> 
#include <complex> 
#include <queue> 
#include <stack> 
#include <cstdlib> 
#include <ctime> 
#include <cstring> 
#include <string.h> 
#include <unordered_set>
#include <unordered_map>
#include <cassert>

using namespace std;

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
typedef unsigned short ushort;
typedef unsigned char uchar;
typedef pair<int, int> ipair;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
#define SIZE(A) ((int)(A.size()))
#define LENGTH(A) ((int)(A.length()))
#define MP(A,B) make_pair(A,B)
const double pi = acos(-1.0);
const double eps = 1e-11;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(a) (a).begin(),(a).end()

template<class T> T sqr(const T &x) { return x * x; }
template<class T> T lowbit(const T &x) { return (x ^ (x - 1))&x; }
template<class T> int countbit(const T &n) { return (n == 0) ? 0 : (1 + countbit(n&(n - 1))); }
template<class T> void ckmin(T &a, const T &b) { if (b<a) a = b; }
template<class T> void ckmax(T &a, const T &b) { if (b>a) a = b; }

namespace standard
{

	const int maxsize = 2048;

	int n;
	vector<int> f[maxsize], g[maxsize];
	int d[maxsize];
	int a[maxsize], b[maxsize];

	bool find(const vector<int>& a, int key)
	{
		auto it = lower_bound(ALL(a), key);
		return it != a.end() && *it == key;
	}
	void add(vector<int>& a, int key)
	{
		auto it = lower_bound(ALL(a), key);
		if (it != a.end() && *it == key) return;
		a.insert(it, key);
	}
	void erase(vector<int>& a, int key)
	{
		auto it = lower_bound(a.begin(), a.end(), key);
		if (it != a.end() && *it == key) a.erase(it);
	}

	bool find(int a, int b)
	{
		return find(f[a], b);
	}
	void add(int a, int b)
	{
		add(f[a], b);
		add(g[b], a);
	}
	void erase(int a, int b)
	{
		erase(f[a], b);
		erase(g[b], a);
	}

	bool find_set(int s)
	{
		FOR(i, s, n) d[i] = 0;
		int sd = 0, pd = s;
		FOR(t, s, n)
		{
			for (int i : g[t]) if (i<pd) ++sd; else ++d[i];
			d[t + 1] -= SIZE(g[t]);
			for (; pd <= t && sd + d[pd] >= 2; sd += d[pd++]);
			if (pd <= t) continue;
			int cnt = 0;
			int last = -1;
			FOR(i, s, t + 1)
			{
				auto it = upper_bound(ALL(f[i]), t);
				if (it == f[i].begin()) continue;
				int next = *(--it);
				if (next <= last) continue;
				a[cnt] = i;
				b[cnt++] = next;
				last = next;
			}
			REP(i, cnt) erase(a[i], b[i]);
			REP(i, cnt - 1) if (a[i + 1] <= b[i]) add(a[i + 1], b[i]);
			return true;
		}
		return false;
	}
	vector<ipair> solve(vector<ipair> a)
	{
		set<int> p;
		for (auto& w : a) if (w.first>w.second) swap(w.first, w.second);
		for (auto w : a) { p.insert(w.first); p.insert(w.second + 1); }
		vector<int> lp(ALL(p));
		n = SIZE(lp);
		map<int, int> wp;
		REP(i, n) wp[lp[i]] = i;
		sort(ALL(a));
		reverse(ALL(a));
		REP(i, n) f[i].clear();
		REP(i, n) g[i].clear();
		for (auto w : a)
		{
			int s = wp[w.first], t = wp[w.second + 1] - 1;
			if (find(s, t)) continue;
			add(s, t);
			find_set(s);
		}
		vector<ipair> ret;
		REP(t, n) for (int s : g[t]) ret.emplace_back(lp[s], lp[t + 1] - 1);
		return ret;
	}

}  // namespace standard

int main()
{
	std::ios_base::sync_with_stdio(false);
	int n;
	while (cin >> n)
	{
		int s, t;
		vector<ipair> a;
		REP(i, n) { cin >> s >> t; a.emplace_back(s, t); }
		vector<ipair> r = standard::solve(a);
		printf("%d\n", SIZE(r));
		for (auto w : r) printf("%d %d\n", w.first, w.second);
	}
	return 0;
}