Rt，只需构造一组菊花图，然后询问完全随机就可以把暴力卡到$O(nm)$。

generator：

#include<bits/stdc++.h>
using namespace std;
int main(){
  cout<<"100000 100000"<<endl;
  for(int i=2;i<=n;i++) cout<<"1 "<<i<<endl;
  for(int i=1;i<=m;i++) cout<<i<<' '<<rand()%201-100<<endl;
}

只是看不惯写LCT要调好久，写暴力直接就能过。