Prazo de entrega recomendado: 31/10/2021

Você implementará um sistema de detecção de ataques DDOS. Será necessário implementar uma árvore binária de busca balanceada.

Os servidores DNS (Domain Name System, ou sistema de nomes de domínio) formam um sistema distribuído responsável por localizar e direcionar os domínios dos sites que digitamos em nossos navegadores para os endereços de IP correspondentes. Por exemplo, associar o domínio mc202.ic.unicamp.br ao endereço IP de um servidor da Universidade.

A resolução de um domínio é hierárquica de forma que um servidor de DNS ou responde uma consulta diretamente, ou a redireciona a um servidor de uma zona inferior. Por exemplo, para resolver o domínio mc202.ic.unicamp.br o servidor de DNS da Unicamp distribui a consulta para o servidor de DNS do IC.

Você é o responsável pela administração dos servidores DNS de uma das zonas com maiores tráfegos do Brasil e percebeu que, nos últimos dias, ocorreram vários ataques a servidores de DNS. Esses ataques consistem em enviar um grande número de consultas para o mesmo domínio, na esperança de sobrecarregar o servidor de DNS desse domínio e, assim, retirar o site do ar.

Para proteger os servidores, você criou uma nova regra de segurança que limita o número de consultas permitidas vindas de um usuário, independentemente do domínio, mesmo que não exista. Desse modo, o usuário que fizer mais consultas do que o limite estabelecido, terá as próximas consultas bloqueadas, de forma a preservar os servidores DNS das zonas inferiores.

Seu objetivo é criar um programa dns.c que permite encontrar os IPs que correspondem a cada domínio solicitado e que por sua vez protege os servidores de ameaças.

Entrada

A primeira linha contém o número $u$ que corresponde ao máximo de consultas DNS permitidas para um usuário.

A segunda linha contém um número $n$ e cada uma das $n$ linhas seguintes contêm o domínio de uma zona DNS cadastrada e o endereço do servido DNS associado. Cada domínio tem no máximo 100 caracteres.

A próxima linha contém um número $m$ e cada uma das próximas $m$ linhas contêm uma consulta com um domínio e o endereço de IP do usuário conforme o exemplo.

Exemplo de entrada

3
2
ic.unicamp.br 143.106.7.54
cecom.unicamp.br 143.106.2.133
11
GET ic.unicamp.br FROM 192.142.133.103
GET ic.unicamp.br FROM 125.132.112.119
GET cecom.unicamp.br FROM 125.132.112.119
GET cecom.unicamp.br FROM 125.132.112.119
GET ic.unicamp.br FROM 119.140.153.128
GET ic.unicamp.br FROM 119.140.153.128
GET cecom.unicamp.br FROM 125.132.112.119
GET ic.unicamp.br FROM 119.140.153.128
GET ic.unicamp.br FROM 115.12.195.25
GET face.com FROM 205.132.225.25
GET ic.unicamp.br FROM 200.192.32.14

Saída

Para cada consulta, deve haver uma linha com uma resposta de acordo com o exemplo de cada caso:

Se o domínio consultado não existe:

NOTFOUND icc.unicamp.br FROM 192.142.133.103

Se o domínio consultado foi encontrado e o usuário não ultrapassou o limite de consultas estabelecido, responde com o endereço do servidor DNS associado:
```
ACCEPTED ic.unicamp.br FROM 115.12.195.25 RESPOND 143.106.7.54
```
Se o usuário ultrapassou o limite de consultas estabelecido:
```
FORBIDDEN ic.unicamp.br FROM 192.142.133.103
```

Exemplo de saída

ACCEPTED ic.unicamp.br FROM 192.142.133.103 RESPOND 143.106.7.54
ACCEPTED ic.unicamp.br FROM 125.132.112.119 RESPOND 143.106.7.54
ACCEPTED cecom.unicamp.br FROM 125.132.112.119 RESPOND 143.106.2.133
ACCEPTED cecom.unicamp.br FROM 125.132.112.119 RESPOND 143.106.2.133
ACCEPTED ic.unicamp.br FROM 119.140.153.128 RESPOND 143.106.7.54
ACCEPTED ic.unicamp.br FROM 119.140.153.128 RESPOND 143.106.7.54
FORBIDDEN cecom.unicamp.br FROM 125.132.112.119
ACCEPTED ic.unicamp.br FROM 119.140.153.128 RESPOND 143.106.7.54
ACCEPTED ic.unicamp.br FROM 115.12.195.25 RESPOND 143.106.7.54
NOTFOUND face.com FROM 205.132.225.25
ACCEPTED ic.unicamp.br FROM 200.192.32.1 RESPOND 143.106.7.54

Critérios

É obrigatório utilizar um árvore binária de busca balanceada.

Dica: Imprima a altura final da árvore. Compare as alturas de uma árvore equilibrada com uma desequilibrada.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

Turma AB: O peso desta tarefa será 4.

Turma E: Você deverá apresentar esta tarefa a um monitor PED. Para isso, você deve procurar atendimento em algum horário com monitor PED e digitar apresentar 13 no canal fila-apresentar.