题意：
给定一个n点m边的无向图，点的编号为[1,n]，边权均为1，可能含有重边。
Q次询问，每次询问给出两个点的编号u、v，若u、v之间最短距离小于等于2，则先输出最短距离，再输出最短距离的方案数，否则输出指定字符串。
题目链接
题解：
在省赛前的训练赛中遇到了这道题，场上看这个奇怪的要求有想过bfs、dp之类的，感觉都没办法做。
第二天晚上补题的时候，在实验室门口来回踱步数十分钟，突然就悟了（雾
首先我们使用unordered_map来存邻接矩阵，其中G[u][v]的值表示u和v直接相连的边的条数，这样对邻接点的查询可以认为是常数级别的。
下面开始进入正题，考虑查询部分。
由题意可知，答案根据最短距离可分为四类：0、1、2、其他。
设查询两点编号为u、v
若u == v
0：最短距离为0，路径数为1
若u != v
若u的邻接点中包含v
1：最短距离为1，路径数为G[u][v]
否则先看（u、v）最短距离是否为2
枚举G[u].size()和G[v].size()中较小的点的邻接点，在另一点的邻接点中查询
设存在k个点是二者的邻接点，若k=0，则说明不存在最短距离为2的路径，输出指定字符串；
若k>0，点分别为，则最短距离为2，路径数为。
易知最短距离为0时，判断u==v求解复杂度为O(1)
最短距离为1时，通过unordered_map所存的邻接矩阵查询，求解复杂度也为O(1)
最短距离不为0或1时，单次复杂度为二者中邻接点较少的邻接点数，这样最坏情况可能高达m*q，貌似并没有什么卵用。这里就是本题的重点了。
考虑把每次查询的答案也用一个unordered_map存下来，这样可以保证已经查询过的点对可以O(1)得到答案。
假设所有查询点对最短距离均至少为2，能构造的最坏情况：
1.每次查询的点对都不相同；
2.所有 被查询的点对中邻接点size较小的 size和尽可能大。
首先考虑每次查询的点对都不相同，，说明我们只需要大约个点即可满足1。
然后通过将m条边平分来使得满足情况2，则每个点邻接点至多约为，则最坏情况下的时间复杂度约为。
因此在用unordered_map存下查询的答案后，本题的时间复杂度可以做到。
至此，本道题就做完了。
（PS：感觉这种算对时间复杂度然后暴力的题在比赛中不算少见，可见优雅的暴力也是ACMer的必备技能啊~
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define m_p make_pair
const int maxn = 1e5+5;
int t,n,m,q,u,v,x,y;
unordered_map<int,int> ans[maxn],G[maxn];//G存邻接矩阵，ans存查询的最短距离 ，3表示除了【0,2】
unordered_map<int,ll> ans1[maxn];//ans1存查询的路径条数，理论上路径条数可能超出int范围
int main(){
// freopen("in.txt","r",stdin);unordered_map<int,int>::iterator it1;scanf("%d",&t);for(int cas=1;cas<=t;cas++){for(int i=1;i<maxn;i++) G[i].clear(),ans[i].clear(),ans1[i].clear();scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){scanf("%d %d",&u,&v);if(u==v) continue;if(G[u].find(v)==G[u].end()) G[u].insert(m_p(v,1)),G[v].insert(m_p(u,1));else G[u][v]++,G[v][u]++;}scanf("%d",&q);cout<<"Case #"<<cas<<":\n";for(int i=1;i<=q;i++){scanf("%d %d",&u,&v);if(u>v) swap(u,v); if(ans[u].find(v)==ans[u].end()){//若此查询第一次出现 if(u==v) ans[u].insert(m_p(v,0)),ans1[u].insert(m_p(v,1));else if(G[u].find(v)!=G[u].end()) ans[u].insert(m_p(v,1)),ans1[u].insert(m_p(v,G[u][v]));else{x=u,y=v;if(G[x].size()>G[y].size()) swap(x,y);for(auto it=G[x].begin();it!=G[x].end();it++){//枚举size较小的x的邻接点 if((it1=G[y].find(it->first))!=G[y].end()){//在y的邻接点中查询 if(ans[u].find(v)==ans[u].end()) ans[u].insert(m_p(v,2)),ans1[u].insert(m_p(v,1ll*(it->second)*(it1->second)));else ans1[u][v]+=1ll*(it->second)*(it1->second);}}if(ans[u].find(v)==ans[u].end()) ans[u].insert(m_p(v,3));}}if(ans[u][v]==3) cout<<"The pair of cities are not connected or too far away.\n";else cout<<ans[u][v]<<" "<<ans1[u][v]<<"\n";}}return 0;
}