CF605B Lazy Student（题解）
Description.
略
Solution.
考虑倒着思考 Kruskal 算法。
按边权从小到大排序。
每次插入一条边。
如果是树边，那就新开节点。
否则在当前节点内任意连边。
这样构造，每次非树边插入都比当前两端小。
所以必然正确。
Coding.
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}/*}}}*/
struct node{int w,id,fr,tw;char fg;}a[100005];int n,m,l=2,r=3,id=1;
int main()
{
read(n),read(m);for(int i=1;i<=m;i++) read(a[i].w),read(a[i].fg),a[i].id=i;
sort(a+1,a+m+1,[](node a,node b){return a.w<b.w||(a.w==b.w&&a.fg>b.fg);});
for(int i=1;i<=m;i++)
{
if(a[i].fg) {a[i].fr=1,a[i].tw=++id;continue;}
if(r>id) return puts("-1"),0;
a[i].fr=l++,a[i].tw=r;if(l==r) r++,l=2;
}sort(a+1,a+m+1,[](node a,node b){return a.id<b.id;});
for(int i=1;i<=m;i++) printf("%d %d\n",a[i].fr,a[i].tw);
return 0;
}