CFR 606 D. Lazy Student ( MST )

http://codeforces.com/contest/606/problem/D
Having MST, we will first want to sort the edges according to their weight. If we assign for each edge from which has smaller weight, if it is to be part of the MST, we will have to have it connecting 2 unique connected components, and vice versa. Soon we should come up with idea of the flower shape. As we go along the sorted edge array, each edge that is going to be part of the MST connects root, which I will define as 1, to a new vertex that has not yet been connected. And for each edge that shall not be chosen, we will connect them with 2 arbitrary vertices that are already part of the MST.

typedef pair< int, pii > tri;
#define tr1 first
#define tr2 second.first
#define tr3 second.second

bool solve(){
    int N, M; cin >> N >> M;

    vector< tri > edge( M );
    for( int i = 0; i < M; ++i ){
        cin >> edge[ i ].tr1 >> edge[ i ].tr2;
        edge[ i ].tr2 ^= 1; // 1 for not used now
        edge[ i ].tr3 = i;
    }
    sort( edge.begin(), edge.end() );

    vp ans( M );
    set< pii > trash; // stores pairs of indices that can join arbitrary edges in future
    int vertex_cnt = 1;
    for( int i = 0; i < M; ++i ){
        if( edge[ i ].tr2 ){ // if not supposed to be picked
            if( trash.empty() ){ // fail to try not to use
                cout << -1 << "\n";
                return false;
            }
            ans[ edge[ i ].tr3 ] = pii( trash.begin()->first, trash.begin()->second );
            trash.erase( trash.begin() );
        } else{ // connect it with root ( 1 ), and new vertex
            ans[ edge[ i ].tr3 ] = pii( 1, ++vertex_cnt );
            for( int i = 2; i < vertex_cnt and trash.size() < M; ++i )
                trash.insert( pii( i, vertex_cnt ) );
                // next time bigger weight unecessary edges comes, connect with these
        }
    }

    if( vertex_cnt < N ){
        cout << -1 << "\n";
        return false;
    }

    for( int i = 0; i < ans.size(); ++i )
        cout << ans[ i ].first << " " << ans[ i ].second << "\n";

    return false;
}