Em uma esquadrilha, existem n pilotos, dos quais m são pilotos principais (co-pilotos não são especificados, mas a numeração implica que pilotos principais têm números menores). Cada aeronave requer exatamente um piloto principal e um co-piloto. No entanto, certos pares de um piloto principal e um co-piloto são incompatíveis devido a restrições operacionais, tornando-os incapazes de voar juntos. O objetivo é determinar o número máximo de pares viáveis para maximizar as aeronaves em operação.

O problema pode ser modelado como um grafo bipartido, onde os pilotos principais e co-pilotos representam partições distintas. As arestas entre elas indicam compatibilidade. A busca por um emparelhamento máximo equivale a encontrar o fluxo máximo em uma rede, com uma fonte conectada a todos os pilotos princiapis e um sumidouro a todos os co-pilotos, todas as arestas tendo capacidade 1.

Formato de Entrada

A primeira linha contém dois inteiros n e m, onde n é o número total de pilotos e m é o número de pilotos principais. As subsequentes linhas contêm pares a b, indicando que o piloto principal a e o co-piloto b podem voar juntos. Os pilotos principais têm números entre 1 e m, e os co-pilotos entre m+1 e n. Restrições: 2 ≤ n ≤ 100.

Formato de Saída

Uma única linha com o número máximo de aeronaves que podem ser emparelhadas.

Exemplo de Entrada

10 5
1 7
2 6
2 10
3 7
4 8
5 9

Exemplo de Saída

4

Implemantação em C++ usando o Algoritmo de Dinic

O código a seguir resolve o problema calculando o fluxo máximo. A rede é construída com uma fonte e um sumidouro, e arestas de capacidade unitária. O algoritmo de Dinic é empregado para eficiência.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAX_NOS = 110;
const int INFINITO = 1e9;

struct Aresta {
    int destino, capacidade, proximo;
};

vector<Aresta> arestas;
int cabecalho[MAX_NOS];
int nivel[MAX_NOS];
int total_arestas;

void adicionarAresta(int origem, int destino, int capacidade) {
    arestas.push_back({destino, capacidade, cabecalho[origem]});
    cabecalho[origem] = total_arestas++;
    arestas.push_back({origem, 0, cabecalho[destino]});
    cabecalho[destino] = total_arestas++;
}

bool bfs(int fonte, int sumidouro) {
    memset(nivel, -1, sizeof(nivel));
    queue<int> fila;
    fila.push(fonte);
    nivel[fonte] = 0;
    while (!fila.empty()) {
        int no = fila.front();
        fila.pop();
        for (int idx = cabecalho[no]; idx != -1; idx = arestas[idx].proximo) {
            int vizinho = arestas[idx].destino;
            if (nivel[vizinho] == -1 && arestas[idx].capacidade > 0) {
                nivel[vizinho] = nivel[no] + 1;
                fila.push(vizinho);
            }
        }
    }
    return nivel[sumidouro] != -1;
}

int dfs(int no, int fluxo, int sumidouro) {
    if (no == sumidouro) return fluxo;
    for (int idx = cabecalho[no]; idx != -1; idx = arestas[idx].proximo) {
        int vizinho = arestas[idx].destino;
        if (nivel[vizinho] == nivel[no] + 1 && arestas[idx].capacidade > 0) {
            int fluxoEnviado = dfs(vizinho, min(fluxo, arestas[idx].capacidade), sumidouro);
            if (fluxoEnviado > 0) {
                arestas[idx].capacidade -= fluxoEnviado;
                arestas[idx ^ 1].capacidade += fluxoEnviado;
                return fluxoEnviado;
            }
        }
    }
    return 0;
}

int dinic(int fonte, int sumidouro) {
    int fluxoMaximo = 0;
    while (bfs(fonte, sumidouro)) {
        int fluxo;
        while ((fluxo = dfs(fonte, INFINITO, sumidouro)) > 0) {
            fluxoMaximo += fluxo;
        }
    }
    return fluxoMaximo;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(cabecalho, -1, sizeof(cabecalho));
    total_arestas = 0;

    int n, m;
    cin >> n >> m;

    int fonte = 0, sumidouro = n + 1;
    for (int i = 1; i <= m; ++i) {
        adicionarAresta(fonte, i, 1);
    }
    for (int i = m + 1; i <= n; ++i) {
        adicionarAresta(i, sumidouro, 1);
    }

    int pilotoPrincipal, coPiloto;
    while (cin >> pilotoPrincipal >> coPiloto) {
        adicionarAresta(pilotoPrincipal, coPiloto, 1);
    }

    cout << dinic(fonte, sumidouro) << endl;
    return 0;
}