1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/* Uva 10020 Minimal coverage */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SWAP_double(a, b, t) {t = a; a = b; b = t;}
#define SWAP_string(a, b, t) {strcpy(t, a); strcpy(a, b); strcpy(b, t);}
#define N 100010
#define SIZE 1000
struct input_data{
	char h[SIZE], t[SIZE];
};
struct input_data ans[N], D[N];
struct segment{
	double head, tail;
};
struct segment S[N];
int s_index[N];
int cmp(const void *a, const void *b){
	int aa = *(int *)a;
	int bb = *(int *)b;
	return ((S[aa].head < S[bb].head)?-1:1);
}
int main(){
	char s1[SIZE], s2[SIZE], tmp_s[SIZE];
	int t, i, r, count;
	double M, a, b, tmp, left, right;
	bool first = false, find;
	scanf("%d", &t);
	while(t--){
		if(first) putchar('\n');
		first = true;
		scanf("%lf", &M);
		i = 0;
		while(scanf("%s%s", s1, s2)){
			sscanf(s1, "%lf", &a);
			sscanf(s2, "%lf", &b);
			if(a == 0 && b == 0) break;
			if(a > b){
				SWAP_double(a, b, tmp);
				SWAP_string(s1, s2, tmp_s);
			}
			if(a > M || b < 0) continue;
			strcpy(D[i].h, s1);
			strcpy(D[i].t, s2);
			S[i].head = a;
			S[i].tail = b;
			s_index[i] = i;
			++i;
		}
		r = i;
		qsort(s_index, i, sizeof(int), cmp);
		for(i=0;i<r;++i){
			sprintf(tmp_s, "%.6lf %.6lf", S[i].head, S[i].tail);
			sscanf(tmp_s, "%lf%lf", &S[i].head, &S[i].tail);
		}
		left = 0.0;
		count = 0;
		for(i=0;i<r;){
			find = false;
			right = 0.0;
			while(i < r){
				if(S[s_index[i]].head <= left && S[s_index[i]].tail > left){
					if(S[s_index[i]].tail > right){
						right = S[s_index[i]].tail;
						ans[count] = D[s_index[i]];
						find = true;
					}
				}
				else break;
				++i;
			}
			if(find){
				++count;
				left = right;
				if(left >= M) break;
			}
			else ++i;
		}
		if(left >= M){
			printf("%d\n", count);
			for(i=0;i<count;++i) printf("%s %s\n", ans[i].h, ans[i].t);
		}
		else printf("0\n");
	}
	return 0;
}