1 /* 2 ID:esxgx1 3 LANG:C++ 4 PROG:hdu3729 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <stack>10 #include <algorithm>11 using namespace std;12 13 #define NSTU    6714 #define NRANK    100000915 16 17 pair<int, int> stu[NSTU];18 char visited[NRANK];19 int matched[NRANK];20 21 int aug(int s)22 {23     for(int t = stu[s].first; t<= stu[s].second; ++t) {24         if (!visited[t]) {25             visited[t] = 1;26             if (matched[t] < 0 || aug(matched[t])) {27                 matched[t] = s;28                 return 1;29             }30         }31     }32     return 0;33 }34 35 int main(void)36 {37     #ifndef ONLINE_JUDGE38     freopen("in.txt", "r", stdin);39     #endif40 41     int T;42     for(scanf("%d", &T); T; --T) {43         int N;44         scanf("%d", &N);45         if(!N) {46             printf("0\n\n");47             continue;48         }49         for(int i=0; i<N; ++i) {50             int x, y;51             scanf("%d%d", &x, &y);52             stu[i].first = x, stu[i].second = y;53         }54 55         memset(matched, -1, sizeof(matched));56 57         int ans[NSTU], _top = 0;58         for(int i=N-1; i>0; --i) {59             if (aug(i))    ans[_top++] = i+1;60             memset(visited, 0, sizeof(visited));61         }62         if (aug(0))    ans[_top++] = 1;63         printf("%d\n", _top);64         while(_top > 1) printf("%d ", ans[--_top]);65         if (_top) printf("%d", ans[--_top]);66         putchar(‘\n‘);67     }68     return 0;69 }