P3906 Geodetic集合

题目描述

图 $\text G$ 是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点 $v,u$ 的最短路径就是从 $v$ 到 $u$ 经过边最少的路径。所有包含在 $v-u$ 的最短路径上的顶点被称为 $v-u$ 的 Geodetic 顶点,这些顶点的集合记作 $I(v,u)$。 我们称集合 $I(v,u)$ 为一个 Geodetic 集合。 例如下图中,$I(2,5)=\{2,3,4,5\}$,$I(1,5)=\{1,3,5\}$,$I(2,4)=\{2,4\}$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/26c7a19d.png) 给定一个图 $\text G$ 和若干点对 $v,u$,请你分别求出 $I(v,u)$。

输入格式

输出格式

说明/提示

对于所有数据,满足 $1\leqslant n\leqslant 40$,$1\leqslant m\leqslant \frac{n(n-1)}2$。