传送门：点击打开链接
题意：一个图n个点m条边，m条边里有n-1条边是一个最小生成树的边，另外n-m+1不是最小生成树的边。边的长度已经告诉你，问能否构造出满足这个最小生成树的图出来
思路：构造一颗深度为2的树，根节点为n，然后有n-1条边，并且构造边的时候把是最小生成树的边和不是的边分开统计，分开按照长度排序
对于一条边不属于最小生成树，如果这条边的端点是(u,v)，那么要求这条边的权值大于等于最小生成树上的(u,v)路径上的边权的最大值。
所以我们可以去枚举哪条边是最大的，然后去把不是最小生成树的边慢慢的添加到图中。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e5 + 5;struct Edge {int u, v;
} E[MX];struct Data {int id, cost;bool operator<(const Data &P)const {return cost < P.cost;}Data(int _id, int _cost) {id = _id; cost = _cost;}Data() {}
} A[MX], B[MX];int n, m;
int r1, r2;int main() {//FIN;while(~scanf("%d%d", &n, &m)) {r1 = r2 = 0;for(int i = 1; i <= m; i++) {int cost, op;scanf("%d%d", &cost, &op);if(op == 1) A[++r1] = Data(i, cost);else B[++r2] = Data(i, cost);}sort(A + 1, A + 1 + r1);sort(B + 1, B + 1 + r2);for(int i = 1; i <= r1; i++) {int id = A[i].id;E[id].u = n; E[id].v = i;}bool sign = true;int a = 2, b = 1;for(int i = 1; i <= r2; i++) {while(a <= r1 && B[i].cost < A[a].cost) {a++; b = a - 1;}if(a == r1 + 1) {sign = false;break;}E[B[i].id].u = E[A[a].id].v;E[B[i].id].v = E[A[b].id].v;if(b == 1) {a++; b = a - 1;} else b--;}if(!sign) printf("-1\n");else {for(int i = 1; i <= m; i++) {printf("%d %d\n", E[i].u, E[i].v);}}}return 0;
}