1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| #include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 3005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int head=1,h[maxn];
struct yyy {
int to,z,w;
void add(int x,int y,int val) {
to=y;z=h[x];h[x]=head;w=val;
}
}a[100005];
void ins(int x,int y,int z) {
a[++head].add(x,y,z);
a[++head].add(y,x,0);
}
int s,t,n,m;
const int inf=1e16;
namespace Dinic {
int deep[maxn],now[maxn];
queue<int>q;
bool bfs(void) {
int i,x;
memset(deep,-1,sizeof(deep));
deep[s]=1;q.push(s);
while (!q.empty()) {
x=q.front();q.pop();now[x]=h[x];
for (i=h[x];i;i=a[i].z) if (a[i].w&&deep[a[i].to]==-1) {
deep[a[i].to]=deep[x]+1;
q.push(a[i].to);
}
}
return deep[t]!=-1;
}
int dfs(int x,int in) {
if (!in||x==t) return in;
int i,sum,res=in;
for (i=now[x];i&&res;i=a[i].z) {
now[x]=i;
if (a[i].w&&deep[a[i].to]==deep[x]+1) {
sum=dfs(a[i].to,min(res,a[i].w));
if (!sum) deep[a[i].to]=-1;
a[i].w-=sum,res-=sum,a[i^1].w+=sum;
}
}
return in-res;
}
int dinic(void) {
int ans=0;
while (bfs()) ans+=dfs(s,inf);
return ans;
}
}
struct egdes{
int x,y,l,p;
}e[maxn];
int sum,in[maxn];
bool check(int val) {
int i;
head=1;
memset(h,0,sizeof(h));
s=0,t=n+m+1;
for (i=1;i<=m;i++) {
ins(s,i+n,1);
ins(i+n,e[i].x,(e[i].l<=val));
ins(i+n,e[i].y,(e[i].p<=val));
if (min(e[i].l,e[i].p)>val) return 0;
}
for (i=1;i<=n;i++) ins(i,t,in[i]/2);
int tmp=Dinic::dinic();
if (tmp==sum) return 1;
else return 0;
}
int vis[1005][1005],len[1005];
int ans[maxn],cnt;
void dfs(int x) {
int i;
for (i=len[x];i<=n;i++) {
len[x]=i+1;
if (vis[x][i]) {
int tmp=vis[x][i];vis[x][i]=0;
dfs(i);
ans[++cnt]=tmp;
}
}
}
signed main(void){
freopen("1.in","r",stdin);
int i,x,y,z;
read(n);read(m);
for (i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].l),read(e[i].p),in[e[i].x]++,in[e[i].y]++;
for (i=1;i<=n;i++)
if (in[i]%2) return puts("NIE"),0;
else sum+=in[i]/2;
int l=0,r=1001,mid;
while (l+1<r) {
mid=l+r>>1;
if (check(mid)) r=mid;
else l=mid;
}
check(r);
for (i=2;i<=m*6;i+=2) if (i%6==4||i%6==0) {
if (a[i^1].w==1) {
int id=(i-1)/6+1;
x=a[i].to;
if (i%6==4) y=a[i+2].to;
else y=a[i-2].to;
vis[x][y]=id;
}
}
printf("%lld\n",r);
dfs(1);
for (i=m;i>=1;i--) printf("%lld ",ans[i]);
return 0;
}
|