F. The Shortest Statement

time limit per test:4 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

You are given a weighed undirected connected graph, consisting of \(n\) vertices and \(m\) edges.

You should answer \(q\) queries, the i-th query is to find the shortest distance between vertices \(u_i\) and \(v_i\).

给定n个点，m条边，q个询问，求每次询问的两点间的最短路。

Input

The first line contains two integers \(n\) and \(m (1≤n,m≤10^5,m−n≤20)\) — the number of vertices and edges in the graph.

Next \(m\) lines contain the edges: the i-th edge is a triple of integers \(v_i,u_i,d_i (1≤u_i,v_i≤n,1≤d_i≤10^9,u_i≠v_i)\). This triple means that there is an edge between vertices ui and vi of weight \(d_i\). It is guaranteed that graph contains no self-loops and multiple edges.

The next line contains a single integer \(q (1≤q≤10^5)\) — the number of queries.

Each of the next \(q\) lines contains two integers \(u_i\) and \(v_i (1≤u_i,v_i≤n)\) — descriptions of the queries.

Pay attention to the restriction \(m−n ≤ 20\).

Output

Print\(q\)lines.

The i-th line should contain the answer to the i-th query — the shortest distance between vertices \(u_i\) and \(v_i\).

Examples

Input

3 3

1 2 3

2 3 1

3 1 5

3

1 2

1 3

2 3

Output

3

4

1

Input

8 13

1 2 4

2 3 6

3 4 1

4 5 12

5 6 3

6 7 8

7 8 7

1 4 1

1 8 3

2 6 9

2 7 1

4 6 3

6 8 2

8

1 5

1 7

2 3

2 8

3 7

3 4

6 8

7 8

Output

7

5

6

7

7

1

2

7

SOLUTION

本题一开始说是要求\(n=10^5\)的多源最短路我被吓到了，裸做单源最短路是不可能的，就又看到了边数的限制：\(m-n\leq 20\)。

这就意味着，在n，m很大的绝大多数情况下，20并不能造成很大的影响。

所以换而言之，这题的模型可以近似地看作是一棵树。因为对于绝大多数的点来说，它们要走的最短路径的确全是树上路径。

树上最短路？求LCA啊。这样我们就可以解决绝大多数的点。

不过那20条边的确不能忽视，因为可能存在更优解要经过那21条边中的一些。而那21条边影响的是什么呢？当然是每条边的两个端点分别关于其他点的最短路啊（存这种端点的时候一定记得要去重！！！）。因为本题的余边只有21条，就可以考虑暴力做至多42遍dijkstra。。。得到了关于以编号为\(j\)的点为起点，图上点\(i\)的单源最短路数组\(dp[i][j]\)。

所以到了最后，我们可以得出，在本题内，最短路的答案要么只从树上的LCA算得，要么就可能走那多余的21条边。

这题是根据数据性质来猜正解的好题。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;#define Min(a,b) ((a
          
           b)?a:b)const int N=101000,MN=45;inline int read(){ int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();} return x*f;}struct EDGE{int nxt,to,w;}e[2*N];int n,m,Q,low[N],vis[N],fa[N][20],head[N],dpt[N],nd[MN],used[N],cnt=0,cnt2=0;LL dist[N][MN],dist2[N];inline void add(int u,int v,int w){e[++cnt].nxt=head[u];e[cnt].to=v;e[cnt].w=w;head[u]=cnt;}void dfs(int u,int fath){ used[u]=1;dpt[u]=dpt[fath]+1;fa[u][0]=fath; for (int i=1;i<=low[dpt[u]];++i){fa[u][i]=fa[fa[u][i-1]][i-1];} for (int i=head[u];i;i=e[i].nxt){ int v=e[i].to,w=e[i].w; if (v==fath) continue; if (!used[v]) {dist2[v]=dist2[u]+w;dfs(v,u);} else{if (used[u]==1) nd[++cnt2]=u,used[u]++; if (used[v]==1) nd[++cnt2]=v,used[v]++;} }}struct NODE{LL d;int u;bool operator< (const NODE &a)const{return d>a.d;}};void dij(int stt,int now){ for (int i=1;i<=n;++i) dist[i][now]=1e18+7; priority_queue
           
             q;q.push((NODE){0,stt});dist[stt][now]=0; memset(vis,0,sizeof(vis)); while (!q.empty()){ NODE ntp=q.top();q.pop(); int u=ntp.u; if (vis[u]) continue; vis[u]=1; for (int i=head[u];i;i=e[i].nxt){ int v=e[i].to,w=e[i].w; if (dist[v][now]>dist[u][now]+w){ dist[v][now]=dist[u][now]+w; q.push((NODE){dist[v][now],v}); } } }}inline int lca(int x,int y){ if (dpt[x]
            
             dpt[y]) {x=fa[x][low[dpt[x]-dpt[y]]];} if (x==y) return x; for (int i=low[dpt[x]];i>=0;--i) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0];}int main(){ int i,j; n=read();m=read();memset(head,0,sizeof(head)); memset(used,0,sizeof(used));memset(dist2,0,sizeof(dist2)); for (i=1;i<=m;++i){ int u=read(),v=read(),w=read();add(u,v,w);add(v,u,w);} low[1]=0;for (i=2;i<=n;++i) low[i]=low[i>>1]+1; dpt[0]=0;dfs(1,0);// sort(nd+1,nd+1+cnt2);cnt2=unique(nd+1,nd+1+cnt2)-nd-1; for (i=1;i<=cnt2;++i) {int stt=nd[i];dij(stt,i);} Q=read(); for (i=1;i<=Q;++i){ int u=read(),v=read(); int ast=lca(u,v); LL DIST=dist2[u]+dist2[v]-dist2[ast]*2; for (j=1;j<=cnt2;++j) DIST=Min(DIST,dist[u][j]+dist[v][j]); printf("%I64d\n",DIST); } return 0;}