Submission #73133180

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=200005,inf=2e9;
int read() {
	static int f=1,c=getchar(),x=0;
	for(f=1; c<=47||c>=58; c=getchar())f=f&&(c!=45);
	for(x=0; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
	return f?x:-x;
}
void print(int x) {
	if(x>9)print(x/10);
	putchar((x%10)|48);
}
int n,m,dis[MAXN],tcnt;
bool vis[MAXN];
vector<pair<int,int>>vec[MAXN];
void dfs(int u) {
	vis[u]=true;
	for(pair<int,int>&tt:vec[u]) {
		int&v=tt.first,&w=tt.second;
		if(!vis[v]) {
			dis[v]=dis[u]^w;
			dfs(v);
		}
	}
}
struct Trie {
	int son[2];
} tr[MAXN*40];
int newnode() {
	++tcnt;
	tr[tcnt].son[0]=tr[tcnt].son[1]=0;
	return tcnt;
}
void Insert(int x) {
	for(int i=18,u=1; i>=0; --i) {
		int&v=tr[u].son[(x>>i)&1];
		if(!v) v=newnode();
		u=v;
	}
}
int query(int x) {
	int u=1,ans=0;
	for(int i=18; ~i; --i)
		if(tr[u].son[(~x>>i)&1])u=tr[u].son[(~x>>i)&1],ans|=1<<i;
		else u=tr[u].son[(x>>i)&1];
	return ans;
}
void solve() {
	tcnt=1,tr[1].son[0]=tr[1].son[1]=0;
	n=read(),m=read();
	for(int i=1,a,b,x; i<=m; ++i) {
		a=read(),b=read(),x=read();
		vec[a].emplace_back(b,x);
		vec[b].emplace_back(a,x);
	}
	dfs(1);
	for(int i=1; i<=n; ++i)Insert(dis[i]);
	int cnt=0,id=-1;
	for(int i=0; i<=n; ++i) 
		if(query(i)<=n) {
			++cnt,id=i;
		}
	if(n&1) {
		if(cnt!=1) printf("-1\n");
		else {
			for(int i=0; i<=n; ++i)vis[i]=false;
			for(int i=1; i<=n; ++i)vis[id^dis[i]]=true;
			for(int i=0; i<=n; ++i)
				if(!vis[i])printf("%d\n",i);
				else vis[i]=false;
		}
	} else if(cnt>0) {
		for(int i=0; i<=n; ++i)vis[i]=false;
		for(int i=1; i<=n; ++i)vis[id^dis[i]]=true;
		for(int i=0; i<=n; ++i)
			if(!vis[i])printf("%d\n",i);
			else vis[i]=false;
	} else printf("-1\n");
	for(int i=1; i<=n; ++i)vec[i].clear(),vis[i]=false;
}
int main() {
	int t=read();
	while(t--)solve();
	return 0;
}

Submission Info

Judge Result