玄关！二分+kruscal WA 30pts

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct edge{
	int u,v,c,id;
}s1[20010],s2[20010];
int n,k,m,bk[20010],fa[10010],tot,as[20010];
bool cmp(edge x,edge y){
	return x.c<y.c;
}
int fd(int x){return fa[x]==x?fa[x]:fa[x]=fd(fa[x]);}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>k>>m;
	int l=1,r=0,ans;
	for(int i=1,u,v,c1,c2;i<m;i++){
		cin>>u>>v>>c1>>c2;
		s1[i].u=u,s1[i].v=v,s1[i].c=c1,s1[i].id=i;
		s2[i].u=u,s2[i].v=v,s2[i].c=c2,s2[i].id=i;
		r=max(r,c1);
	}
	sort(s1+1,s1+m,cmp);
	sort(s2+1,s2+m,cmp);
	while(l<=r){
		int mid=l+r>>1,cnt=0;
		for(int i=1;i<=n;i++)fa[i]=i,bk[i]=0;
		for(int i=1;i<m;i++){
			if(s1[i].c>mid)break;
			int u=fd(s1[i].u),v=fd(s1[i].v);
			if(u!=v){
				bk[s1[i].id]=1;
				fa[u]=v;
				cnt++;
			}
		}
		if(cnt<k){l=mid+1;continue;}
		for(int i=1;i<m;i++){
			if(s2[i].c>mid)break;
			int u=fd(s2[i].u),v=fd(s2[i].v);
			if(u!=v&&!bk[s2[i].id]){
				bk[s2[i].id]=2;fa[u]=v;
			}
		}
		cnt=0;
		for(int i=1;i<=n;i++)if(fd(i)==i)cnt++;
		if(cnt>1)l=mid+1;
		else{
			r=mid-1;ans=mid;
			for(int i=1;i<m;i++)as[i]=bk[i];
		}
	}
	cout<<ans<<"\n";
	for(int i=1;i<m;i++)if(as[i])cout<<i<<" "<<as[i]<<"\n";
	return 0;
}