记录编号	354030	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	CodeLyoko	是否通过	通过
代码语言	Pascal	运行时间	0.121 s
提交时间	2016-11-19 17:01:31	内存使用	3.75 MiB

type
  edge=record
  from,too:longint;
  len:longint;
end;
var
  edges:array[0..100000]of edge;
  p,r:array[0..100000]of longint;
  n,m,i,x,y,z,tpb,q:longint;
  from,too,len,next:array[0..100000]of longint;
  first,deep,fa,stfa:array[0..10010]of longint;


procedure qsort(l,r:longint);
var
  i,j,m:longint;
begin
  m:=edges[(l+r)div 2].len;
  i:=l;
  j:=r;
  repeat
    while edges[i].len>m do inc(i);
    while edges[j].len<m do dec(j);
    if i<=j then begin
      edges[0]:=edges[i];
      edges[i]:=edges[j];
      edges[j]:=edges[0];
      inc(i);
      dec(j);
    end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

function find(x:longint):longint;
begin
  if p[x]<>x then p[x]:=find(p[x]);
  find:=p[x];
end;

procedure union(a,b:longint);
var
  t:longint;
begin
  a:=find(a);
  b:=find(b);
  if r[a]>r[b] then begin
    t:=a;
    a:=b;
    b:=t;
  end;
  if r[a]=r[b] then inc(r[a]);
  p[a]:=b;
end;

procedure addedge(a,b,c:longint);
begin
  inc(tpb);
  from[tpb]:=a;
  too[tpb]:=b;
  len[tpb]:=c;
  next[tpb]:=first[a];
  first[a]:=tpb;
end;

procedure kk;
var
  e:longint;
begin
  e:=0;
  for i:=1 to m do begin
    if e=n-1 then exit;
    with edges[i] do begin
      if find(from)<>find(too)then begin
        union(from,too);
        inc(e);
        addedge(from,too,len);
        addedge(too,from,len);
      end;
    end;
  end;
end;

procedure dfs(v,father,ll,dep:longint);
var
  p:longint;
begin
  deep[v]:=dep;
  fa[v]:=father;
  stfa[v]:=ll;
  p:=first[v];
  while p<>0 do begin
    if(deep[too[p]]=0)then dfs(too[p],v,len[p],dep+1);
    p:=next[p];
  end;
end;

function lca(a,b:longint):longint;
var
  min:longint;
begin
  if deep[a]<deep[b] then begin
    min:=a;
    a:=b;
    b:=min;
  end;
  min:=999999;
  while deep[a]>deep[b] do begin
    if stfa[a]<min then min:=stfa[a];
    a:=fa[a];
  end;
  while a<>b do begin
    if stfa[a]<min then min:=stfa[a];
    if stfa[b]<min then min:=stfa[b];
    a:=fa[a];
    b:=fa[b];
  end;
  exit(min);
end;

begin
  assign(input,'truck.in');
  reset(input);
  assign(output,'truck.out');
  rewrite(output);
  readln(n,m);
  for i:=1 to m do begin
    readln(x,y,z);
    edges[i].from:=x;
    edges[i].too:=y;
    edges[i].len:=z;
  end;
  for i:=1 to n do
    p[i]:=i;
  qsort(1,m);
  readln(q);
  tpb:=0;
  kk;
  for i:=1 to n do
    if deep[i]=0 then dfs(i,0,0,1);
  for i:=1 to q do begin
    readln(x,y);
    if find(x)<>find(y) then writeln(-1)
    else writeln(lca(x,y));
  end;
  close(input);
  close(output);
end.