时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
给定一个n个点m条边的无向联通图G=(V,E)，满足G中不存在自环。
你需要求G的一个生成树T，使得T的权值和在[L,R]内。
求满足条件的T的个数。
输入描述:
第一行两个正整数n,m，表示点数和边数。
接下来m行，每行三个整数u,v,val，描述一条边。
接下来一行一个正整数q，表示询问的组数。
接下来q行，每行两个整数L,R，意义如“题目描述”
输出描述:
对于每一组询问，输出一个非负整数表示答案。
示例1
输入
复制
3 5
1 2 1
1 3 2
1 3 7
2 3 4
2 3 3
2
3 11
6 9
示例2
输入
复制
5 8
1 2 3
1 3 10
1 4 4
1 5 2
2 4 7
2 5 5
2 3 6
3 4 8
1
15 30
说明
对于30%的数据，n<=8，L,R<=100
对于50%的数据，n<=10，m<=15
对于70%的数据，1<=L,R<=100000
对于另外10%的数据，val(u,v)两两相等，L=R。
对于100%的数据，1<=u,v<=n<=20，1<=m<=25，1<=q<=10000，1<=L<=R<=10^8，1<=val(u,v)<=10^7。
对于100%的数据，读入的所有L,R中，maxR-minL<=10^6。
请注意算法的常数优化。