#include <cstdlib>
#include <iostream>
#include <vector>

class Tab {
	private:
		int *tab;
	public:
		bool fin;
		Tab(void) { 
			tab= new int[2];
		};
		Tab(const Tab& t) {
			tab= new int[2];
			tab[0]= t[0];
			tab[1]= t[1];
			fin= t.fin;
		}
		~Tab(void) { 
			delete [] tab;
		};
		int operator [](int k) const {
			return tab[k];
		};
		int& operator [](int k) {
			return tab[k];
		};
};

bool equiv(int n, int p, int q, std::vector<Tab>& f)
{
	if ( n==0 )
		return f[p].fin==f[q].fin;
	else
		return f[p].fin==f[q].fin
				&& equiv(n-1, f[p][0], f[q][0], f) 
				&& equiv(n-1, f[p][1], f[q][1], f);
}

int main(int argc, char *argv[])
{
	std::vector<Tab> f;
	while ( std::cin.peek()!='\n' ) {
		Tab t;
		std::cin >> t[0] >> t[1];
		t.fin= false;
		while (std::cin.peek()!='\n') {
			int c= std::cin.get();
			if (c!=' ' )
				t.fin= true;
		}
		std::cin.get();
		f.push_back(t);	
	}

	for (auto& t : f)
		std::cout<< t[0]<< '\t'<< t[1]<< (t.fin? "*" : "") << std::endl;

	std::vector<int> C, E;
	for (int p=0; p<f.size(); ++p) {
		C.push_back(p);
		E.push_back(-1);
	}

	int n= 0;
	for (int p=0; p<f.size(); ++p) {
		if (C[p]==p) {
			for (int q=p+1; q<f.size(); ++q)
				if (equiv(f.size(), p, q, f))
					C[q]= C[p];
			E[p]= n++;
		}
	}

	std::cout << "-------\n";
	for (int q=0; q<f.size(); ++q)
		std::cout << q << ":\t" << C[q] << "\t" << E[q] << std::endl;

	for (int q=0; q<f.size(); ++q)
		for (int s=0; s<2; ++s)
			f[q][s]= E[C[f[q][s]]];

	std::cout << "-------\n";
	for (int p=0; p<f.size(); ++p)
		if (C[p]==p)
			std::cout<< E[p] << ":\t" <<f[p][0]<< '\t'<< f[p][1]
					<< (f[p].fin? "*" : "") << std::endl;

	return EXIT_SUCCESS;
}