#include<iostream>
#include<cstring>
using namespace std;

const int N = 510, M = 1e5 + 10;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];//match表示女生节点匹配的男生节点是什么
bool st[N];//st表示女生节点是否被预定

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])
        {
            st[j] = true;
            //如果当前j女生未被预定，如果被预定了，帮与她匹配的男生节点match[j]找其他可匹配的女生
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    //找不到能匹配的女生
    return false;
}

int main()
{
    scanf("%d%d%d", &n1, &n2, &m);
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    int res = 0;
    //遍历所有男生节点
    for(int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if(find(i)) res ++;
    }
    printf("%d", res);
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u, int c)
{
    color[u] = c;
    //遍历与当前节点连接的节点
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3 - c)) return false;//将下一节点染上与当前节点不同颜色
        }
        //如果下一节点与当前节点颜色相同
        else if (color[j] == c) return false;
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1 , sizeof h);

    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bool flag = true;
    //遍历每个点
    for(int i = 1; i <= n; i++)
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }

    if(flag) puts("Yes");
    else puts("No");

    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int p[N];//存储父节点

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for(int i = 1; i <= n; i++) p[i] = i;

    int res = 0, cnt = 0;
    for(int i = 0; i < m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if(cnt < n - 1) return INF;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if(t == INF) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for(int i = 0; i < n ; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
        {
            //找到与集合最近的点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];
        st[t] = true;
        //更新集合外的点，到集合的最小距离
        for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);

    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if(t == INF) puts("impossible");
    else printf("%d", t);

    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], ne[N], e[N], idx;
int d[N], q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i++)
        if(!d[i])
            q[++ tt] = i;

    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(-- d[j] == 0) q[++ tt] = j;
        }
    }
    return tt == n - 1;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        //d[i]代表每个点的入度
        d[b] ++;
    }
    if(!topsort()) puts("-1");
    else 
    {
        for(int i = 0; i < n; i ++) printf("%d ", q[i]);
    }
    return 0;
}

#include<iostream>
#include<cstring>

using namespace std;
const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    memset(d, -1, sizeof d);

    d[1] = 0;
    while(hh <= tt)
    {
        int t = q[hh ++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++ tt] = j;
            }
        }
    }
    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    printf("%d", bfs());
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
int ans = N;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
    st[u] = true;
    int size = 0, sum = 1;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;

        int s = dfs(j);//返回的是以u为根的子树，除u外的节点数之和
        size = max(size, s);//记录连通子图的最大节点数
        //sum记录u为根的子树的节点和。包括u，因为要挖掉u
        sum += s;
    }
    //将u为根的子树，挖掉u后最大 连通子图的节点数size，与去掉u为根的这个子树之后，
    //剩余节点数比较。样例，u=4时，4的父亲节点，并且其他与之相连的节点总数就是n - sum。
    size = max(size, n - sum);
    //每一次遍历都比较剩余连通子图的最大节点数，取最小。
    ans = min(ans, size);
    return sum;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1 , sizeof h);
    for(int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    printf("%d", ans);
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
int ans = N;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
    st[u] = true;
    int size = 0, sum = 0;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(st[j]) continue;

        int s = dfs(j);
        size = max(size, s);
        sum += s;
    }

    size = max(size, n - sum - 1);
    ans = min(ans, size);
    return sum + 1;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1 , sizeof h);
    for(int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs(1);

    printf("%d", ans);
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

//从任意的i到任意的j，最短路径有两种情况
//1、i直接到j
//2、i经过若干的点到j
//即式子d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
//一眼看去，感觉只是多考虑的一个点k，i->k,k->j是不是比i->j短，但展开看就发现，其实是考虑了1到k-1的节点总和
//有4个点，1,2,3,4;当k=3 d[1][4] = min(d[1][4], d[1][3] + d[3][4]),
//d[1][3]可能是d[1][2] + d[2][3], d[1][4] = min(d[1][4], d[1][2] + d[2][3] + d[3][4])
//例子只供理解思路，不是真实例子。
void floyd()
{
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    //初始化
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while(m --)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
    }

    floyd();

    while(Q --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int t = d[a][b];
        if(t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;

    //这里dist不初始化，随便什么值都可以，现在dist[]的值是0，只有碰到负权边才会更新，开始记录cnt。
    //有dist这个前提在，如果负环在源节点无法到达的地方，那么可能无法从源节点更新到负环。
    //因此需要把每个点都先放入队列，以免从初始节点开始就结束了，找不到后面的点。
    //如样例所示，如果不把每个点都放入队列，dist[2]不会更新，也就无法遍历到2->3的负权边。
    for(int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }

    while(q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}