#P3906. Geodetic集合

Geodetic集合

题目描述

G\text G 是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点 v,uv,u 的最短路径就是从 vvuu 经过边最少的路径。所有包含在 vuv-u 的最短路径上的顶点被称为 vuv-u 的 Geodetic 顶点,这些顶点的集合记作 I(v,u)I(v,u)

我们称集合 I(v,u)I(v,u) 为一个 Geodetic 集合。

例如下图中,I(2,5)={2,3,4,5}I(2,5)=\{2,3,4,5\}I(1,5)={1,3,5}I(1,5)=\{1,3,5\}I(2,4)={2,4}I(2,4)=\{2,4\}

给定一个图 G\text G 和若干点对 v,uv,u,请你分别求出 I(v,u)I(v,u)

输入格式

第一行为两个整数 n,mn,m,分别表示图 G\text G 的顶点数和边数(顶点编号为 1n1\sim n)。
接下来 mm 行,每行两个整数 a,ba,b,表示 顶点 aabb 之间有一条无向边。
m+2m+2 行有一个整数 kk,表示给定的点对数。
接下来 kk 行,每行两个整数 v,uv,u,表示每个点对的起点和终点。

输出格式

kk 行,对于输入文件中每一个点对 v,uv,u,按顶点顺序一行输出 I(v,u)I(v,u) 里面的所有点的编号。

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4
2 3 4 5
1 3 5
2 4

提示

对于所有数据,满足 1n401\leqslant n\leqslant 401mn(n1)21\leqslant m\leqslant \frac{n(n-1)}2