#include<cstdio>#include<algorithm>#include<cstring>#define F(i,a,b) for(int i=a;i<=b;i++)#define mst(a,b) memset(a,b,sizeof(a))using namespace std;typedef pair<int,int>P;const int N=1e5+200,DEG=18;int g[N],v[N*2],nxt[N*2],ed,n,m,q,eed,cnt,id[N],Q[N];int dep[N],fa[N][DEG],dfn[N],idx,d[201][N];P vec[N];bool vis[N];inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}inline void up(int &a,int b){if(a>b)a=b;}void dfs(int u=1,int pre=0){    dep[u]=dep[pre]+1,fa[u][0]=pre,dfn[u]=++idx;    F(i,1,DEG-1)fa[u][i]=fa[fa[u][i-1]][i-1];    for(int i=g[u];i;i=nxt[i])if(!dfn[v[i]])dfs(v[i],u);    else if(v[i]!=pre&&dfn[v[i]]<dfn[u])vec[++eed]=P(u,v[i]);}int LCA(int a,int b){    if(dep[a]>dep[b])a^=b,b^=a,a^=b;    if(dep[a]<dep[b])F(i,0,DEG-1)if((dep[b]-dep[a])&(1<<i))b=fa[b][i];    if(a!=b)for(int i=DEG-1;i<0?a=fa[a][0]:0,i>=0;i--)    if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];    return a;}void bfs(int *d,int S){    mst(vis,0);    int head=1,tail=0,now;    Q[++tail]=S,vis[S]=1,d[S]=0;    while(head<=tail)for(int i=g[now=Q[head++]];i;i=nxt[i])    if(!vis[v[i]])vis[v[i]]=1,d[v[i]]=d[now]+1,Q[++tail]=v[i];}int main(){    while(~scanf("%d%d%d",&n,&m,&q))    {        int x,y;ed=idx=eed=cnt=0;        mst(g,0),mst(dfn,0),mst(fa,0),mst(id,0);        F(i,1,m)scanf("%d%d",&x,&y),adg(x,y),adg(y,x);        dfs();        F(i,1,eed)        {            if(!id[vec[i].first])id[vec[i].first]=++cnt,bfs(d[cnt],vec[i].first);            if(!id[vec[i].second])id[vec[i].second]=++cnt,bfs(d[cnt],vec[i].second);        }        F(i,1,q)        {            scanf("%d%d",&x,&y);            int ans=dep[x]+dep[y]-2*dep[LCA(x,y)];            F(j,1,eed)            {                int u=id[vec[j].first],v=id[vec[j].second];                up(ans,d[u][x]+d[v][y]+1),up(ans,d[v][x]+d[u][y]+1);            }            printf("%d\n",ans);        }    }    return 0;}

#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>typedef long long LL;const LL maxn=1e5+10;const LL mod=1e9+7;using namespace std;struct Tree{    LL to,next,c;} edge[maxn*2];LL Inv[30*maxn];LL tot,head[maxn];LL jc[maxn*30];LL sum;void Init(){    Inv[0]=1;    Inv[1] = 1;    for(LL i=2; i<25*maxn; i++)        Inv[i] = (mod-mod/i)*Inv[mod%i]%mod;    for(LL i=2; i<25*maxn; i++)        Inv[i] = (Inv[i-1]*Inv[i])%mod;}void init(){    tot=0;    memset(head,-1,sizeof(head));}void add_edge(LL u,LL v,LL c){    edge[tot].to=v;    edge[tot].c=c;    edge[tot].next=head[u];    head[u]=tot++;}void init2(){    jc[0]=1;    for(LL i=1; i<maxn*30; i++)        jc[i]=((jc[i-1]*i)%mod);}LL road[maxn];void  dfs(LL u,LL pre){    road[u]=0;    for(LL i=head[u]; i!=-1; i=edge[i].next)    {        LL v=edge[i].to;        if(v==pre) continue;        dfs(v,u);        road[u]+=edge[i].c;        sum=(((sum*jc[edge[i].c*2])%mod)*Inv[edge[i].c])%mod;        sum=((sum*  jc[(road[v]+edge[i].c-1)]%mod)*Inv[edge[i].c-1] )%mod;        sum=(sum*Inv[road[v]])%mod;    }    sum=(sum*jc[road[u]])%mod;}int main(){    Init();    init2();    LL n,u,v,c;    while(scanf("%lld",&n)!=-1)    {        sum=1;        init();        for(LL i=1; i<n; i++)        {            scanf("%lld%lld%lld",&u,&v,&c);            add_edge(u,v,c);            add_edge(v,u,c);        }        dfs(1,0);        printf("%lld\n",sum);    }    return 0;}