Prefácio: Provavelmente existe uma solução mais rápida para este problema. Podemos considerar que os limites aplicados aqui tornam o problema "fácil".
Este problema foi inspirado pela matéria de Sistemas Distribuídos.
A solução do juiz consiste em criar um grafo como mostrado na figura a partir do formato desorganizado de entrada. Cada vértice do grafo representa um produto cartesiano entre as pessoas $$$u$$$ e seus respectivos índices de acontecimento $$$i$$$, obtendo assim um grafo com $$$nm$$$ vértices.
Primeiramente, as arestas correspondentes a ações subsequentes da mesma pessoa são colocadas logo no processamento da entrada.
Em seguida, é feito um processamento que consiste em uma busca em profundidade utilizando de um vetor de espera de recebimento wait_recv, um vetor de espera de envio wait_send e um vetor de posição pos. O funcionamento consiste em iterar até o final utilizando o vetor pos (de forma que se o processo aparecer de novo para ser processado, ele continua de onde parou), fazendo a seguinte rotina:
Para realizar as consultas, fazemos duas operações de busca em profundidade no grafo direcionado construído acima. Se é possível atingir o vértice $$$(j, f_j)$$$ por meio de $$$(i, f_i)$$$, significa que $$$i$$$ aconteceu antes. Se é possível atingir o vértice $$$(i, f_i)$$$ por meio de $$$(j, f_j)$$$, significa que $$$j$$$ aconteceu antes. Se é impossível de atingir os vértices nesses dois casos, não podemos concluir nada sobre a ordem dos acontecimentos.
Visto que fazemos essas buscas em profundidade a cada consulta, nossa solução tem complexidade $$$O(qnm)$$$.