E小红的无向图构造

#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
    int n,m;
    cin>>n>>m;
    if(m < n-1){    //不能构成图
        cout<<"-1"<<endl;
        return;
    }
    vector<int> g[n+10];    //用来存层次（最短路长度）相同的点
    vector<int> a(n+1,0);
    int ma = -1;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
        ma = max(ma,a[i]);
        g[a[i]].push_back(i);   //层次（最短路长度）相同的点放在一起
    }
    vector<pair<int,int>> ans;
    for (int i = 1; i <= ma; ++i) {
        if(g[i-1].empty()){
            cout<<"-1";         //如果某个层次的上一层次没有点就输出-1
            return;
        }
    }
    for (int i = 1; i <= ma; ++i) {
        for (auto k : g[i]) {
            ans.push_back({g[i-1][0],k});   //开始构造，层次相同的点都连到上一层次的第一个点
        }
    }
    /**
     * 第一种情况，相同层次之间也可以连边，不影响最短路长度，边数等于m就退出
     */
    if(ans.size() < m){    //注意先判断一下此时边数是否小于m
        for (int i = 1; i <= ma; ++i) {
            for (int j = 1; j < g[i].size(); ++j) {
                for (int k = j - 1; k >= 0; --k) {
                    ans.push_back({g[i][j], g[i][k]});  //相同层次的点连起来
                    if (ans.size() >= m) break;
                }
                if (ans.size() >= m) break;
            }
            if (ans.size() >= m) break;
        }
        /**
         * 第二种情况 每个层次的点与上一层次的除了第一个点连接
         */
        for (int i = 1; i <= ma; ++i) {
            for (int j = 1; j < g[i - 1].size(); ++j) {
                for (int k = 1; k < g[i].size(); ++k) {
                    ans.push_back({g[i - 1][j], g[i][k]});
                    if (ans.size() >= m) break;
                }
                if (ans.size() >= m) break;
            }
            if (ans.size() >= m) break;
        }
    }
    if(ans.size() < m){ //边数小于m输出-1
        cout<<"-1";
    } else{
        for (auto i : ans) {    //输出边
            cout<<i.first<<" "<<i.second<<endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}