C Linguagem C - Grafos - Linha de Metros

heyJames · 11 de julho de 2023

Linhas de Metrô

Por Maratona de Programação da SBC 2018 Brazil

Timelimit: 1

O sistema de metrô de uma grande cidade é formado por um conjunto de estações e por túneis que ligam alguns pares de estações. O sistema foi desenhado de forma que existe exatamente uma sequência de túneis ligando qualquer par de estações. As estações nas quais apenas um túnel chega são chamadas de terminais. Há várias linhas de trens que fazem viagens de ida e volta entre duas estações terminais, transitando pelo caminho único entre elas. A população está reclamando das linhas atuais e, por isso, o prefeito ordenou uma reformulação total das linhas. Como o sistema possui muitas estações, nós precisamos ajudar os engenheiros que estão tentando decidir quais pares de terminais passarão a definir uma linha.

A figura ilustra um sistema onde as estações terminais são mostradas como círculos preenchidos e as não-terminais são mostradas como círculos vazios. Na parte esquerda, veja que se o par (A,B) definir uma linha e o par (C,D) definir outra, elas não terão qualquer estação em comum. Mas, na parte direita, podemos ver que se os pares (E,F) e (G,H) definirem duas linhas, elas terão duas estações em comum.

Dada a descrição do sistema de túneis e uma sequência de Q consultas constituídas de dois pares de terminais, seu programa deve computar, para cada consulta, quantas estações em comum as linhas definidas pelos dois pares teriam.

Entrada

A primeira linha da entrada contém dois inteiros N (5 ≤ N ≤ 105 ) e Q (1 ≤ Q ≤ 20000), representando respectivamente o número de estações e o número de consultas. As estações são numeradas de 1 até N. Cada uma das N −1 linhas seguintes contém dois inteiros distintos U e V , 1 ≤ U, V ≤ N, indicando que existe um túnel entre as estações U e V . Cada uma das Q linhas seguintes contém quatro inteiros distintos A, B, C e D (1 ≤ A, B, C, D ≤ N), representando uma consulta: as duas linhas de trem são definidas pelos pares (A, B) e (C, D).

Saída

Para cada consulta, seu programa deve imprimir uma linha contendo um inteiro representando quantas estações em comum teriam as duas linhas de trem definidas pela consulta.

Exemplo:

Entrada:

10 4

1 4

4 5

3 4

3 2

7 3

6 7

7 8

10 8

8 9