My T-shirt suits me

Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of six, and NM. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.

You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N M, there can be some remaining T-shirts.

Input 

The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1N36, and indicates the number of T-shirts. Number M, 1M30, indicates the number of volunteers, with NM. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).

Output 

For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.

Sample Input 

 
3
18 6
L XL
XL L
XXL XL
S XS
M S
M L
6 4
S XL
L S
L XL
L XL
6 1
L M

Sample Output 

 
YES
NO
YES

---

照理講應該不會過得, 不過測資很水, 用 dfs 就過了, 就不必使用最大匹配了 

#include <stdio.h>
#include <string.h>
const char s[][4] = {"XXL", "XL", "L", "M", "S", "XS"};
int code(const char *str) {
    static int i;
    for(i = 0; i < 6; i++)
        if(!strcmp(s[i], str))
            return i;
}
int map[30][2], flag, used[6];
int n, m, t;
void dfs(int idx) {
    if(flag)
        return;
    if(idx == m) {
        flag = 1;
        return;
    }
    if(used[map[idx][0]] > 0) {
        used[map[idx][0]]--;
        dfs(idx+1);
        used[map[idx][0]]++;
    }
    if(used[map[idx][1]] > 0) {
        used[map[idx][1]]--;
        dfs(idx+1);
        used[map[idx][1]]++;
    }
}
int main() {
    char str[20];
    int i, num;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        n = n/6;
        for(i = 0; i < m; i++) {
            scanf("%s", str);
            num = code(str);
            map[i][0] = num;
            scanf("%s", str);
            num = code(str);
            map[i][1] = num;
        }
        for(i = 0; i < 6; i++)
            used[i] = n;
        flag = 0;
        dfs(0);
        if(flag)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

---