题意：
一个n个节点的图，有m条边，已知这个图的一个mst
现在如果我们知道这个图的m条边，和知道mst的n-1条边是哪些，问能不能构造出一个满足条件的图
思路：排序+构造
数组deg[i]表示节点i此时还可以1～i-1中的多少条边相连
由于：deg[i]=i-1时，最低可以和1连接，=i-2时，最低可以和2连接
所以如果我们知道i和deg[i]的话，我们就知道这一次i要和哪一个节点连接，
就可以我构造出来了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib> #define fir first
#define sec second using namespace std; const int MAXN = + ; struct Edge
{
int is,w,id;
};
Edge edge[MAXN];
int deg[MAXN];
pair<int,int>res[MAXN]; bool cmp(Edge x,Edge y)
{
if(x.w == y.w)
return x.is > y.is;
return x.w < y.w;
} inline int lb(int x)
{
return x&(-x);
} void update(int x,int add,int n)
{
while(x <= n){
deg[x] += add;
x += lb(x);
}
} int query(int x)
{
int ret = ;
while(x > ){
ret += deg[x];
x -= lb(x);
}
return ret;
} pair<int,int> find_edge(int num,int n)
{
int l=,r=num;
while(r-l > ){
int mid=(l+r)>>;
if(query(mid) <= )
l = mid;
else
r = mid;
}
int tmp;
if(query(r) == )
tmp = r;
else
tmp = l;
tmp++;
int tmp_deg = query(tmp);
pair<int,int> ret = make_pair(tmp-tmp_deg,tmp);
update(tmp,-,n);
return ret;
} void solve(int n,int m)
{
memset(deg,,sizeof deg);
int num = ;
int sum = ;
bool flag = true;
sort(edge+,edge+m+,cmp); for(int i=;i<=m;i++){
if(edge[i].is){
num++;
update(num,num-,n);
//for(int j=1;j<=n;j++){
// printf("deg[%d] = %d\n",j,query(j) - query(j-1));
//}
sum += num - ;
res[edge[i].id] = make_pair(,num);
}
else{
if(sum <= ){
flag = false;
break;
}
else{
sum--;
res[edge[i].id] = find_edge(num,n);
}
}
}
if(!flag)
puts("-1");
else{
for(int i=;i<=m;i++){
printf("%d %d\n",res[i].fir,res[i].sec);
}
}
return ;
} int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d %d",&edge[i].w,&edge[i].is);
edge[i].id = i;
} solve(n,m); return ;
}