#题目大意 给定若干的边权和这条边是否在最小生成树里的信息，要求复原出一个图，使其的最小生成树之一符合输入

#思路 将所有边按照边权排序，同时使得被选中的边尽量靠前 然后我们可以让最小生成树是一颗菊花树 答案不存在的情况就是，到排序后的第 \(i(i−1)/2\) 条边的时候已经得到了一个 \(i\) 个节点的完全图，但得到的边是未被选中的 添加不在最小生成树上的边可以按照 \((2,3),(2,4),(3,4),(2,5),(3,5),(4,5),(2,6)\ldots\) 这样的顺序 #Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
const int maxm = 100000 + 5;
struct edge{
    int id, w, sel;
    int u, v;
}e[maxm];
int n, m;
int maxconn = 1;
int curru = 2, currv = 2;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        e[i].id = i;
        cin >> e[i].w >> e[i].sel;
    }
    sort(&e[0], &e[m],
            [](const edge &a, const edge &b)
            {return a.w < b.w || (a.w == b.w && a.sel > b.sel);});
    for (int i = 0; i < m; i++)
    {
        if (e[i].sel)
        {
            maxconn++;
            e[i].u = maxconn;
            e[i].v = 1;
        } else {
            if (curru == currv)
            {
                currv ++;
                curru = 2;
            }
            if (currv > maxconn) {cout << "-1\n";return 0;}
            e[i].u = currv;
            e[i].v = curru;
            curru++;
        }
    }
    sort(&e[0], &e[m],
            [](const edge &a, const edge &b)
            {return a.id < b.id;});
    for (int i = 0; i < m; i++)
        cout << e[i].u << " " << e[i].v << "\n";
    return 0;
}