[Cerc2015]Export Estimate

时间限制：10s 空间限制：128MB

题目描述

给你一个n个点m条边的无向图，每条边有权值，我们可以选择一个整数lim来生成一个新的图，过程如下：

1.先将原图中边权小于lim的边删掉

2.依次从1到n枚举每个点

（a）如果这个点没有边于它相连，这个点将会被删去

（b）如果这个点只与两条不相同的边x，y相连，设这两条边的另一个点分别为a，b，如果a，b和这个点都不相同（a，b可以相同），则依次做如下操作：

（i）删去边x，y

（ii）删去这个点

（iii）在a，b之间建立一条新的边

下面这个例子lim=95：

数据保证原图没有重边和自环，但不保证经过如上操作后的图没有重边和自环。

现在我们想知道当lim取若干值时，由原图生成的新图的点数和边数是多少。

输入格式

第一行两个数n，m，表示原图有n点m条边。

接下来m行，每行三个数a，b，c，表示a和b之间有一条边权为c的双向边。

接下来一行一个数q，表示有q次询问。

接下来一行q个数，k1，k2，...，kq。

输出格式

总共q行，每行两个数，表示lim取ki时，生成的新图的点数和边数

样例输入

Sample Input1: 
6 7 
1 2 20 
2 3 80 
2 5 100 
3 5 50 
3 4 100 
5 6 90 
4 6 100 
4 
25 75 85 95 
Sample Input2: 
10 14 
2 7 150 
1 2 100 
2 3 150 
3 1 200 
1 4 60 
4 5 20 
2 5 100 
5 6 90 
6 7 120 
7 5 130 
6 8 50 
8 9 200 
9 10 200 
10 7 200 
5 
300 50 95 100 110

样例输出

Sample Output1: 
2 3 
1 1 
2 1 
4 2 
Sample Output2: 
0 0 
6 9 
4 5 
4 5 
5 4 

数据范围： 
1<=n<=300000 
1<=m<=300000 
0<=c<=300000 
1<=q<=300000 
0<=ki<=300000

提示

没有写明提示

题目来源

没有写明来源