最大流的应用，最小路径覆盖，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1422
/*距离标号的最大流*/
#include <stdio.h>

const int LEN = 500;

const int MAX = 0x7fffffff;

struct
{
    int c;
    int f;
}map[LEN][LEN]; /*邻接矩阵*/

struct
{
    int node;
}nearl[LEN][LEN];/*邻接链表,第一个表示最后一个位置*/

void initm ( int n )
{
    
    for ( int i=0; i<n; i++ )
    {
        nearl[i][0].node = 0;
        for ( int j=0; j<n; j++ )
        {
            map[i][j].c = map[i][j].f = 0;
        }
    }
}

int dis[LEN];//标号的数组

void initd ( int n )
{
    
    for ( int i=0; i<n; i++ )
    {
        dis[i] = -1;
    }
}

int que[LEN];
int head, tail;

void initq ()
{
    
    head = 0;
    tail = -1;
}

void inq ( int in )
{
    
    que[++tail] = in;
}

void outq ( int *out )
{
    
    *out = que[head++];
}

int testempty ()
{
    
    return head > tail ? 1 : 0;
}

int mark ( int s, int t, int n )/*进行距离标号*/
{
    
    int out;
    int in;
    
    initd ( n );
    
    initq ();
    inq ( s );
    dis[s] = 0;
    while ( ! testempty () )
    {
        outq ( &out );
        if ( out == t )
        {
            return 1;
        }
        for ( int p=1; p<=nearl[out][0].node; p++ )
        {
            in = nearl[out][p].node;
            if ( map[out][in].c > map[out][in].f || map[in][out].f > 0 )
            {
                if ( dis[in] == -1 )
                {
                    dis[in] = dis[out] + 1;
                    inq ( in );
                }
            }
        }
    }
    return 0;
}

typedef struct
{
    int now;
    int from;
    int weight;
}type;
type stack[LEN];//用于记录路径的堆栈
int top;

void inits ()
{
    
    top = -1;
}

void push ( type *in )
{
    
    top ++;
    stack[top].now = in->now;
    stack[top].from = in->from;
    stack[top].weight = in->weight;
}

void pop ()
{
    top --;
}

int gettop ()
{
    
    return stack[top].now;
}

int minest ( int a, int b )
{
    
    return a < b ? a : b;
}

int ad ()/*流量调整函数*/
{
    
    int now, from;
    int min = MAX;
    int i;
    for ( i=1; i<=top; i++ )
    {
        now = stack[i].now;
        from = stack[i].from;
        if ( stack[i].weight > 0 )
        {
            min = minest ( min, map[from][now].c-map[from][now].f );
        }
        else
        {
            min = minest ( min, map[now][from].f );
        }
    }
    
    for ( i=1; i<=top; i++ )
    {
        now = stack[i].now;
        from = stack[i].from;
        if ( stack[i].weight > 0 )
        {
            map[from][now].f += min;
        }
        else
        {
            map[now][from].f -= min;
        }
    }
    return min;
}

int maxflow ( int s, int t, int n )/*最小费用最大流函数*/
{
    
    int p;
    int i;
    int flow = 0;    
    type in;
    
    while ( mark ( s, t, n ) )
    {
        inits ();
        in.now = s;
        in.from = -1;
        in.weight = 1;
        push ( &in );
        while ( ( p = gettop () ) != t )
        {
            for ( i=1; i<=nearl[p][0].node; i++ )
            {
                int v = nearl[p][i].node;
                if ( map[p][v].c > map[p][v].f )
                {
                    if ( dis[p] == dis[v] - 1 )
                    {
                        in.now = v;
                        in.from = p;
                        in.weight = 1;
                        push ( &in );
                        break;
                    }
                }
                if ( map[v][p].f > 0 )
                {
                    if ( dis[p] == dis[v] - 1 )
                    {
                        in.now = v;
                        in.from = p;
                        in.weight = -1;
                        push ( &in );
                        break;
                    }
                }
            }
            if ( i > nearl[p][0].node  )
            {
                dis[p] = n;
                pop ();
            }
        }
        flow += ad ();
    }
    return flow;
}

void add ( int a, int b, int c )//增加一条边
{
    
    if ( ! map[a][b].c && ! map[b][a].c )
    {
        int p = nearl[a][0].node;
        nearl[a][++p].node = b;
        nearl[a][0].node ++;
        p = nearl[b][0].node;
        nearl[b][++p].node = a;
        nearl[b][0].node ++;
    }
    map[a][b].c += c;
}

int main ()
{

    int t, n, m;
    int b, e;

    while ( scanf ( "%d", &t ) != EOF )
    {
        while ( t -- )
        {
            scanf ( "%d%d", &n, &m );
            
            initm ( 2 * n + 2 );

            for ( int i=1; i<n+1; i++ )
            {
                add ( 0, i, 1 );
            }

            for ( i=0; i<m; i++ )
            {
                scanf ( "%d%d", &b, &e );

                add ( b, e+n, 1 );
            }

            for ( i=n+1; i<2*n+1; i++ )
            {
                add ( i, 2*n+1, 1 );
            }

            printf ( "%d\n", n - maxflow ( 0, 2*n+1, 2*n+2 ) );
        }
    }
    return 0;
}