#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int> pp;
const int s = 9;

vector<int> color(vector< vector<int> > graph, int n){
	// basic graph coloring algorithm
	vector<bool> colors(n, true);
	vector<int> result(n,-1);
	result[0] = 0;// color the first vertex with color 0
	for ( int i=0; i<n;i++){
		vector<int>::iterator it;
		for(it = graph[i].begin();it!=graph[i].end();it++)
			if (result[*it] != -1) // if the vertex is colored with a color then make the color unavailable
				colors[result[*it]] = false;// for coloring the current vertex

			// find the first available color
			int clr = 0;
			for (; clr<n;clr++)
				if (colors[clr])
					break;
			result[i] = clr;// color the vertex with the first available color
		for(it = graph[i].begin();it!=graph[i].end();it++){
			// reset the available colors
			if (result[*it] != -1)
				colors[result[*it]] = true;
		}
	}
	return result;
}

vector<int> WPA(vector< set<int> > graph, int n){
	// modified implementation of Welsh-Powell algorithm
	priority_queue<pp, vector<pp> >pq;
	vector<bool> colors(n, true);
	vector<int> result(n*n,-1);
	for (int i=0; i<graph.size(); i++){
		pq.push(make_pair(graph[i].size(), i));
	}

	result[pq.top().second] = 0;// color the first vertex with color 0
	pq.pop();
	while ( !pq.empty()){
		int i = pq.top().second;
        //cout << i <<endl;
		pq.pop();
		//cout << i << " ";
		set<int>::iterator it;
		for(it = graph[i].begin();it!=graph[i].end();it++)
			if (result[*it] != -1) // if the vertex is colored with a color then make the color unavailable
				colors[result[*it]] = false;// for coloring the current vertex

			// find the first available color
			int clr = 0;
			for (; clr<n;clr++)
				if (colors[clr])
					break;
			result[i] = clr;// color the vertex with the first available color
		for(it = graph[i].begin();it!=graph[i].end();it++){
			// reset the available colors
			if (result[*it] != -1)
				colors[result[*it]] = true;
		}
	}
	return result;
}

vector< vector<int> > makeGraph(int m, int n){
	// make the adjacency list of the graph
	vector< vector<int> > graph(n+1);
	for(int j = 0; j<m;j++){
		int u,v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	return graph;
}

vector < set <int> > makeBoard(){
    vector< set<int> >graph(s*s);
    for (int i=0;i<(s*s);i++){
        int r=(i/9);
        int c=(i%9);
        for(int j=0;j<s;j++){
            int v=(j*s)+c;
            if (v!=i)
                graph[i].insert(v);
            v=(i-c+j);
            if (v!=i)
                graph[i].insert(v);
        }
        int sr = (r-(r%3));
        int sc = (c-(c%3));
        for(int l=0;l<3;l++){
            int j=((sr+l)*s+sc);
            for(int k=0;k<3;k++){
                if ((j+k)!=i)
                    graph[i].insert(j+k);
            }
        }
    }
    return graph;
}

int main(){
	int n,m;
	//cin >> n >> m;
	//vector< vector<int> > graph = makeGraph(m,n);
	vector< set<int> > g = makeBoard();
	for(int i=0;i<g.size();i++){
        set<int>::iterator it;
		for(it = g[i].begin();it!=g[i].end();it++)
            cout << *it <<" ";
        cout << endl << i <<endl;
	}
	//vector<int> result = WPA(graph,n);
	vector<int> result = WPA(g,s);

	for ( int i=0;i<(s*s);i++){
		cout <<"Vertex: "<< i << " -----> color: " <<result[i] << endl;
	}
	return 0;
}