#include using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vectorvint; typedef pairpint; typedef vectorvpint; templateinline void chmin(A &a,B b){if(a>b)a=b;} templateinline void chmax(A &a,B b){if(aque; rep(i,q){ if(who[x[i]][0]!=-1)continue; who[0][x[i]]=i; que.push(pint(0,x[i])); } while(que.size()){ int d,v; tie(d,v)=que.front(); que.pop(); if(d==2)continue; for(auto u:G[v]){ if(who[d+1][u]!=-1)continue; who[d+1][u]=who[d][v]; que.push(pint(d+1,u)); } } rep(i,N){ int k=10; rep(j,3)if(who[j][i]!=-1)chmin(k,who[j][i]); if(k==10)continue; if(x[k]==i)continue; A[x[k]]+=A[i]; A[i]=0; } rep(i,q){ for(int j=0;j