9576 책 나눠주기

#include <stdio.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int from[1005];
int student[1005];
vector<int> adj[1005];
 
int dfs(int x) {
    if (student[x] == 1)
        return 0;
 
    student[x] = 1;
    for (int i = 0; i < adj[x].size(); i++) {
        int tmp = adj[x][i];
        
        if (from[tmp] == 0) {
            from[tmp] = x;
            return 1;
        }
        else {
            if (dfs(from[tmp]) == 1) {
                from[tmp] = x;
                return 1;
            }
        }
    }
    return 0;
}
 
int main() {
    int t;
    scanf("%d", &t);
 
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        // 원래대로 초기화
        fill(from, from + 1005, 0);
        for (int i = 0; i < 1005; i++) {
            adj[i].clear();
        }
 
        for (int i = 1; i <= m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            for (int j = a; j <= b; j++)
                adj[i].push_back(j);
        }
 
        int rst = 0;
        for (int i = 1; i <= m; i++) {
            fill(student, student + 1005, 0);
 
            if (dfs(i) == 1)
                rst++;
        }
        printf("%d\n", rst);
    }
}