Submission #6378002

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;

vector<int> adj[100010];
int color[100010];
pair<int,int> edges[100010];

//0 keluar 1 masuk

void dfs(int u,int col)
{
	color[u] = col;
	if (adj[u].size() % 2 == 1)
		color[u] = 0;
	for (int i = adj[u].size() % 2 ; i < adj[u].size() ; i++)
	{
		if (color[adj[u][i]] == color[u])
		{
			if ((adj[u].size() % 2) == (adj[adj[u][i]].size() % 2))
			{
				cout << -1 << endl;
				exit(0);
			}
		}
		if (color[adj[u][i]] == -1)
			dfs(adj[u][i],1 - color[u]);
	}
	if (adj[u].size() % 2 == 1)
	{
		if (color[adj[u][0]] == 1)
		{
			cout << -1 << endl;
			exit(0);
		}
		if (color[adj[u][0]] == -1)
			dfs(adj[u][0],0);
	}
}

map< pair<int,int>,bool > sudah;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	if (m % 2 == 1)
	{
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1 ; i <= m ; i++)
	{
		int ta,maudy;
		cin >> ta >> maudy;
		adj[ta].push_back(maudy);
		adj[maudy].push_back(ta);
		edges[i] = {ta,maudy};
	}
	for (int i = 1 ; i <= n ; i++) if (adj[i].size() % 2 == 1)
	{
		for (int j = 0 ; j < adj[i].size() ; j++)
		{
			if (adj[adj[i][j]].size() % 2 == 1)
			{
				cout << -1 << endl;
				return 0;
			}
		}
	}
	memset(color,-1,sizeof(color));
	bool ada = 0;
	for (int i = 1 ; i <= n ; i++)
	{
		if (adj[i].size() % 2 == 1)
		{
			dfs(i,0);
			ada = 1;
			break;
		}
	}
	if (!ada)
		dfs(1,0);
	for (int i = 1 ; i <= n ; i++)
	{
		for (int j = 0 ; j < adj[i].size() ; j++)
		{
			if (sudah[{i,adj[i][j]}] || sudah[{adj[i][j],i}]) continue;
			sudah[{i,adj[i][j]}] = sudah[{adj[i][j],i}] = 1;
			if (adj[i].size() % 2 == 1)
			{
				if (j == 0)
					cout << adj[i][j] << " " << i << endl;
				else
					cout << i << " " << adj[i][j] << endl;
			}
			else
			{
				if (color[i] == 0)
					cout << i << " " << adj[i][j] << endl;
				else
					cout << adj[i][j] << " " << i << endl;		
			}
		}
	}
}

Submission Info

Judge Result