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
| #pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e3+10,M=2e4+10,inf=2e9;
int n,m,in[N],out[N],S,T,vis[M],cnt,g[N];
struct Edge{int x,y,v1,v2;}e[M];
namespace Flow{
int fir[N],nxt[(M+N)<<1],son[(M+N)<<1],w[(M+N)<<1],tot,cur[N],dis[N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0;}
#define to son[i]
queue<int> q;
I bool bfs(){W(!q.empty()) q.pop();q.push(S);memset(dis,-1,sizeof(dis));dis[S]=0;W(!q.empty()){RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>0&&dis[to]==-1) dis[to]=dis[u]+1,q.push(to);}return ~dis[T];}
I int dfs(CI x,CI flow){if(x==T) return flow;RI i,d,now=flow;for(i=cur[x];i;i=nxt[i]) if(cur[x]=nxt[i],w[i]>0&&dis[to]==dis[x]+1){d=dfs(to,min(w[i],now));w[i]-=d,w[i^1]+=d,now-=d;if(!now) break ;}return flow-now;}
I int F(){RI i,Ans=0;W(bfs()){for(i=1;i<=cnt;i++) cur[i]=fir[i];Ans+=dfs(S,inf);}return Ans;}
I void C(){memset(fir,0,sizeof(fir)),tot=1;}
}
I bool chk(CI x){
memset(in,0,sizeof(in)),memset(out,0,sizeof(out)),Flow::C(),cnt=n,S=++cnt,T=++cnt;RI i,X=0;for(i=1;i<=m;i++) max(e[i].v1,e[i].v2)<=x?out[e[i].x]++,in[e[i].y]++,Flow::Add(e[i].y,e[i].x,1),0:e[i].v1<=x?out[e[i].x]++,in[e[i].y]++:e[i].v2<=x&&(out[e[i].y]++,in[e[i].x]++);
for(i=1;i<=n;i++) if(abs(in[i]-out[i])&1) return 0;else in[i]>out[i]&&(Flow::Add(S,i,abs(in[i]-out[i])>>1),X+=abs(in[i]-out[i])>>1),in[i]<out[i]&&(Flow::Add(i,T,abs(in[i]-out[i])>>1),0);return Flow::F()==X;
}
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<PA> G[N];
vector<int> stk;
#define pb push_back
I void Add(CI x,CI y,CI z){G[x].pb(MP(y,z));}
I void DFS(CI x){PA i;for(RI j=0;j<G[x].size();j=max(j+1,g[x])) if(i=G[x][j],!vis[i.se]) vis[i.se]=1,g[x]=j+1,DFS(i.fi),stk.pb(i.se);}
I void Prt(CI X){RI i,j;for(assert(chk(X)),i=1,j=2;i<=m;i++) max(e[i].v1,e[i].v2)<=X?(Flow::w[j]?Add(e[i].x,e[i].y,i):Add(e[i].y,e[i].x,i),j+=2):e[i].v1<=X?Add(e[i].x,e[i].y,i),0:(e[i].v2<=X&&(Add(e[i].y,e[i].x,i),0));for(i=1;i<=n;i++) sort(G[i].begin(),G[i].end());DFS(1);}
I void Out(){reverse(stk.begin(),stk.end());for(auto i:stk) write(i),pc(' ');pc('\n');}
int main(){
freopen("euler.in","r",stdin),freopen("euler.out","w",stdout);
RI i,l=0,r=1000,mid,X=2e9;for(srand(time(NULL)),srand(rand()),srand(rand()),read(n,m),i=1;i<=m;i++) read(e[i].x,e[i].y,e[i].v1,e[i].v2),l=max(l,min(e[i].v1,e[i].v2)),r=max(r,max(e[i].v1,e[i].v2));
W(l<=r) chk(mid=l+r>>1)?X=mid,r=mid-1:l=mid+1;return X>=2e9?puts("NIE"):(writeln(X),Prt(X),Out(),0),clear(),0;
}
|