Algoritmo Spaceuber: Maximização de Viagens Espaciais

Algoritmo 5 Spaceuber Expert Tempo máximo de execução 1s DESCRIÇÃO Descrição Agora que Oto está a uma distância segura do domínio confederado ele precisa de um trabalho para sobreviver Como ele tem uma nave a sua disposição ele pensou em trabalhar como Spaceuber fazendo viagens espaciais Como as distâncias no espaço são muito maiores que na Terra e os dias são mais curtos as viagens costumam ser mais longas e por isso as solicitações de viagem são agendamentos para o dia seguinte A Spaceuber costuma pagar para os pilotos um valor que cobre o custo da viagem incluindo o deslocamento para uma próxima viagem mais um valor fixo assim os pilotos tendem a escolher as viagens que vão fazer de modo que eles consigam fazer o máximo de viagens possível Oto agora precisa de uma forma de escolher quais viagens atenderá no dia seguinte de modo que o número de viagens e seus ganhos seja maximizado Como foi dito as viagens são agendadas para o dia seguinte mas não para um horário específico assim caso um piloto queira atender uma determinada viagem o aplicativo da Spaceuber informa automaticamente no final daquele dia com base no intinerário do piloto para o dia seguinte em que horário o piloto passará para buscar cada passageiro Isso permite que os pilotos possam definir seus intinerários sem se preocupar com os tempos de viagem O aplicativo da Spaceuber também reescreve os números dos setores nas solicitações de viagem de modo que o setor de origem sempre possua um número menor que o setor de destino e de modo que se o setor x aparece em duas solicitações eles representam o mesmo setor Pelas regras da Spaceuber cada piloto pode passar por cada setor uma única vez em cada dia sendo que é possível deixar um passageiro e já pegar o passageiro da viagem seguinte no mesmo setor Uma vez definidas quais viagens serão atendidas o aplicativo as coloca em ordem do menor número de origem até o maior número de destino Formato de entrada A primeira linha da entrada contém um número inteiro N 1 N 10000 A seguir são apresentadas N linhas contendo cada uma um par de números inteiros i e j 1 i j 100000 indicando o setor de origem e de destino de cada viagem Formato de saída A saída é dada por um único número inteiro indicando o maior número de viagens que Oto consegue atender respeitando as regras das Spaceuber Exemplos de Entrada 10 2 7 2 5 1 4 3 8 3 6 5 12 7 10 8 12 8 15 10 16 Saída 3 Entrada 5 1 5 2 7 6 10 6 13 11 13 Saída 3