題意：

一個(gè) 包含 \(n\) 個(gè)點(diǎn) \(m\) 條邊的簡(jiǎn)單無向連通圖。現(xiàn)在，刪掉其中的一些邊讓度數(shù)為奇數(shù)的點(diǎn)盡可能多。

輸出要?jiǎng)h掉哪些邊, 用一個(gè)長(zhǎng)為 \(m\) 的 01串 表示, 第 \(i\) 位為 \(1\) 表示不刪第 \(i\) 條邊, 為 \(0\) 表示刪掉第 \(i\) 條邊。并滿足這個(gè) 01串 的字典序盡量大。

對(duì)于 \(100 \%\) 的數(shù)據(jù), \(2 \leq n \leq 6 \times 10^{5}, n-1 \leq m \leq 9 \times 10^{5}, 0 \leq x_{i} \leq y_{i}<n\), 對(duì)任意 \(i \neq j\), 有 \(\left(x_{i}, y_{i}\right) \neq\left(x_{j}, y_{j}\right)\), 且保證給定的圖連通。

題解：

先考慮是樹有什么性質(zhì)。若點(diǎn)數(shù)為偶數(shù)，那么度數(shù)為偶數(shù)的點(diǎn)必然有偶數(shù)個(gè)。因?yàn)槎葦?shù)和一直為偶數(shù)。

那么我們可以考慮任意兩兩偶數(shù)點(diǎn)配對(duì)，其路徑上所有邊狀態(tài)翻轉(zhuǎn)。那么這樣答案是一定的。因?yàn)榭紤]一個(gè)邊子樹內(nèi)的情況，若子樹內(nèi)有偶數(shù)個(gè)度數(shù)為偶數(shù)的點(diǎn)，那么其外側(cè)也會(huì)有偶數(shù)個(gè)度數(shù)為偶數(shù)的點(diǎn)，那么一定會(huì)越過這條邊偶數(shù)次，反之則一定是奇數(shù)次，所以是確定的。

根據(jù)這一點(diǎn)，我們可以快速判斷每個(gè)點(diǎn)的狀態(tài)，只需要記錄子樹內(nèi)部的度數(shù)為偶數(shù)的點(diǎn)的和即可，我們把這個(gè)東西給成點(diǎn)權(quán)，這樣方便做題。

接下來考慮奇數(shù)個(gè)點(diǎn)的情況，先還是判斷每條邊是否可能刪除。但是注意，這時(shí)候我們構(gòu)造出來的東西就不大一樣了，我們?cè)?dfs 中讓子樹內(nèi)部的度數(shù)為偶數(shù)的點(diǎn)的和為偶數(shù)的點(diǎn)保留，其他刪除，那么最終 \(1\) 號(hào)點(diǎn)的度數(shù)一定為偶數(shù)，其他都是奇數(shù)。因?yàn)檫f歸的時(shí)候還是保持的相同策略，所以結(jié)果不變。

這樣雖然滿足了度數(shù)為奇數(shù)的點(diǎn)盡可能多，但是沒有滿足字典序盡量大，考慮處理這個(gè)東西。

我們思考怎么改變答案，就是讓 \(1\to u\) 鏈上翻轉(zhuǎn)一下，看這個(gè)答案是否比原來大。可以樹剖線段樹 \(+\) hash 來做這玩意，但是我們有更好的方法。

我們按照邊的編號(hào)從小到大搞，這個(gè)時(shí)候我們能不刪除就不刪除，顯然滿足了題意。考慮若出現(xiàn)了要?jiǎng)h除的邊，考慮能否換掉原來度數(shù)為偶數(shù)的點(diǎn)，使其不用刪掉。這時(shí)我們進(jìn)行分類。

設(shè)原來的點(diǎn)為 \(h\) 現(xiàn)在的點(diǎn)為 \(v\)，那么我們已經(jīng)翻轉(zhuǎn)了 \(1\to h\) 的點(diǎn)權(quán)。

\(v\) 對(duì)應(yīng)的邊本來要?jiǎng)h掉：

• 若 \(v\) 為 \(h\) 的祖先，那么自然不用刪了，因?yàn)榉D(zhuǎn)了。
• 若 \(v\) 和 \(h\) 沒有祖先后代關(guān)系，那么該刪就要?jiǎng)h。
• 若 \(v\) 在 \(h\) 子樹內(nèi)但是 \(1\to v\) 的路徑上有編號(hào)比 \(v\) 小的點(diǎn)是沒有刪的，那么我們還是要?jiǎng)h這一點(diǎn)，因?yàn)椴粍h前面更小的邊就要保留了，不符合貪心。
• 若 \(v\) 在 \(h\) 子樹且 \(1\to v\) 的路徑上所有編號(hào)比 \(v\) 小的點(diǎn)都刪除了，我們翻轉(zhuǎn)邊權(quán)并讓 \(h=v\)。

\(v\) 對(duì)應(yīng)的邊本來要保留：

• 若 \(v\) 是 \(h\) 的祖先，那么翻轉(zhuǎn)了，必須刪掉。

• 否則我們保留，并且將其記錄下來，表示沒有刪除。

接下來考慮圖，其實(shí)很簡(jiǎn)單，我們都證明了答案最大只要是樹就可以，那我們讓圖上挖一顆樹，使得其最小編號(hào)最大，這不就是最大生成樹嗎，所以還是在樹上做。

code：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lbt(x) (x&(-x))
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=2e6+10;
int n,m,k,T,a[N],fa[N],out[N],dfn[N];
int cnt,t[N],val[N],ans[N],vv[N],idx[N];
vector<pii> g[N];struct node{int u,v;}e[N];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int dfs(int u,int fa){
	dfn[u]=++cnt;int nw=0;
	for(pii t:g[u]){
		int v=t.fi,id=t.se;if(v==fa) continue;
		int p=dfs(v,u);if(!p) ans[id]=1;
		nw+=p;idx[id]=v;
	}out[u]=cnt;return (((val[u]&1)^1)+nw)&1;
}
void upd(int i,int x){while(i<N){t[i]+=x;i+=lbt(i);}}
int sc(int i){int ans=0;while(i>0){ans+=t[i];i-=lbt(i);}return ans;}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>m;
    rep(i,1,n) fa[i]=i;
    rep(i,1,m){
    	int x,y;cin>>x>>y;
    	e[i]={x+1,y+1};
	}per(i,m,1){
		int u=e[i].u,v=e[i].v;
		val[u]++,val[v]++;
		if(find(u)!=find(v)){
			vv[i]=1;fa[find(u)]=find(v);
			g[u].pb({v,i});g[v].pb({u,i}); 
		}else ans[i]=1;
	}dfs(1,0);
	if(n%2==0){
		rep(i,1,m) cout<<ans[i];
	}else{
		int h=1;
		rep(i,1,m){
			int v=idx[i];
			if(!vv[i]){cout<<1;continue;}
			if(!ans[i]){
				if(dfn[v]<=dfn[h]&&dfn[h]<=out[v]){cout<<1;continue;}
				if(dfn[v]<dfn[h]||out[h]<dfn[v]||sc(dfn[v])>0) cout<<0;
				else h=v,cout<<1;
			}else{
				if(dfn[h]<dfn[v]||out[v]<dfn[h]){
					cout<<1;upd(dfn[v],1);upd(out[v]+1,-1);
				}else cout<<0;
			}
		}
	}
	return 0;
}