题解：CF587D Duff in Mafia
最优解已经被我们占领拉
首先二分答案，将权值
考虑分类讨论.
1.如果一个点连了 >2 条同色边一定无解
证明：选和不选两种状态，鸽巢原理得知至少有一个状态选了两条边，无解.
2.如果一个点连了 2 条同色死边一定无解
似乎不需要证明.
3.如果一个点对于两种不同颜色都有 2 条边，那么一定无解
证明：每一种颜色只能选一条边不选一条边，那么这个点就会被选两次.
（具体可以自行画图证明）
那么我们对于一个点所连的边就只有三种情况.
1.一个同色活边+死边，若干不同色活边死边
此时这个同色的活边必选，所以其他边全都不能要.
2.两个同色活边，若干不同色活边死边
此时只能二选一，跟其他边也没关系，也全都不要.
3.若干不同色活边死边
没有同色边意味着可以选这些边中的至多一个.
（具体可以自行画图理解）
用 2-SAT 算法可以实现.
但是注意到情况三需要边两两加限制，时间复杂度为
这个时候正常人会掏出前缀优化见图，但是我不会.
但是这样常数翻了个若干倍.
我们将 2-SAT 中的连边称作限制.
那么存在定理.
4.无限制的边一定可以不选
证明：
假设不选它之后会冲突.
那么说明有一个同颜色共顶点的边也没选.
可是如果存在同颜色共顶点的边，那么要么是无解要么是情况一或二，存在限制.
与条件矛盾.
所以我们把没有限制的边也全不要，剩下的边的数量很少.
暴力添加限制可做.
代码：（358ms 最优解榜三）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m;
struct edge{int u,v,c,w,id;}e[N];
bool cmp_w(edge a,edge b){return a.w<b.w;}
vector<int> H,G[N];
struct node{
int v,c,id;
node(int vv=0,int cc=0,int iid=0){v=vv; c=cc; id=iid;}
};
vector<node> T[N];
void read(){
map<int,int> mp;
mp.clear();
int num=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
int col;
cin>>e[i].u>>e[i].v>>col>>e[i].w;
e[i].id=i;
if(!mp[col]) mp[col]=++num;
e[i].c=mp[col];
}
sort(e+1,e+1+m,cmp_w);
for(int i=1;i<=m;i++){
T[e[i].u].push_back(node(e[i].v,e[i].c,i));
T[e[i].v].push_back(node(e[i].u,e[i].c,i));
}
}
namespace tarjan{
int tot,dfn[N],low[N];
int top,num,st[N],scc[N],act[N];
void dfs(int x){
act[x]=1; st[++top]=x;
dfn[x]=++tot; low[x]=tot;
for(int y:G[x]){
if(!dfn[y]){
dfs(y);
low[x]=min(low[x],low[y]);
}else if(act[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
++num;
while(1){
int u=st[top]; top--;
act[u]=0; scc[u]=num;
if(u==x) break;
}
}
}
void clear(){
top=num=tot=0;
for(int i=1;i<=m+m;i++){
dfn[i]=low[i]=scc[i]=act[i]=0;
}
}
bool sol(){
clear();
for(int i=m+m;i>=1;i--) if(!dfn[i]) dfs(i);
for(int i=1;i<=m;i++) if(scc[i]==scc[i+m]) return 0;
H.clear();
for(int i=1;i<=m;i++) if(scc[i]<scc[i+m]) H.push_back(i);
return 1;
}
}
namespace build{
vector<int> A[N];
int id,cnt,num,Max,col,box[N],g[N],f[N];
void add(int x,int y){G[x].push_back(y);}
void clear(){
for(int i=1;i<=m;i++) box[i]=0;
for(int i=1;i<=n;i++) f[i]=0,A[i].clear();
for(int i=1;i<=m+m;i++) G[i].clear();
for(int i=1;i<=m;i++) g[i]=0;
}
void upd(int c){
box[c]++;
if(box[c]>Max) Max=box[c],col=c,cnt=1;
else if(box[c]==Max) cnt++;
}
bool sol1(){
for(int i=id+1;i<=m;i++) add(i,i+m);
for(int x=1;x<=n;x++){
Max=cnt=col=num=0;
for(node p:T[x]) upd(p.c);
if(Max>2) return 0;
if(Max==2&&cnt>1) return 0;
int idx=0,idy=0,idz=0,u,v;
for(node p:T[x])if(col==p.c){
if(p.id>id) num++,idy=p.id;
else{
if(idx==0) idx=p.id,u=p.v;
else idz=p.id,v=p.v;
}
}
if(Max==2){
if(num==2) return 0;
if(num==1){
g[idx]=1; f[u]=idx;
add(idx+m,idx);
// A[u].push_back(idx);
}else{
g[idx]=g[idz]=1;
add(idx+m,idz);
add(idx,idz+m);
add(idz,idx+m);
add(idz+m,idx);
// A[u].push_back(idx);
// A[v].push_back(idz);
}
}
for(node p:T[x]) box[p.c]=0;
}
for(int i=1;i<=m;i++) if(g[i]==1){
A[e[i].u].push_back(i);
A[e[i].v].push_back(i);
}
for(int x=1;x<=n;x++){
if(f[x]){
for(node i:T[x]) if(i.id!=f[x])add(i.id,i.id+m);
continue;
}
for(int i:A[x]) for(int j:A[x]) if(i!=j){
add(i,j+m);
add(j,i+m);
}
}
return 1;
}
bool work(int nzq){
id=nzq;
clear();
if(!sol1()) return 0;
return 1;
}
}
bool check(int id){
if(!build::work(id)) return 0;
if(!tarjan::sol()) return 0;
return 1;
}
void work(){
int L=0,R=m+1;
while(L<R){
int mid=(L+R)>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
if(L==m+1){
cout<<"No\n";
}else{
cout<<"Yes\n";
check(L);
cout<<e[L].w<<' '<<H.size()<<'\n';
for(int p:H) cout<<e[p].id<<' ';
cout<<'\n';
}
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen("nzq.in","r",stdin);
// freopen("nzq.out","w",stdout);
read();
work();
return 0;
}