#include <algorithm>
#include <climits>
#include <fstream>
#include <sstream>
#include <string>
#include <tuple>
#include <set>
#include <vector>

using namespace std;

// Базовый класс представления
class IGRepr {
public:
	virtual void from_file(string filepath) = 0;
	virtual void to_file(string filepath,bool is_oriented, bool is_weighted) = 0;
	virtual void add_edge(int vertex_a, int vertex_b, int weight) = 0;
	virtual void remove_edge(int vertex_a, int vertex_b) = 0;
	virtual int change_weight(int vertex_a, int vertex_b, int new_weight) = 0;
	virtual vector<tuple<int,int,int>> get_edges() = 0;
	virtual ~IGRepr() {};
	virtual int count_vertices() = 0;
};

// Представление в виде матрицы смежности
class AdjMatrix: public IGRepr {
private:
	vector<vector<int>> matrix;
public:
	AdjMatrix(int n = 0);
	virtual void from_file(string filepath) override;
	virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
	virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
	virtual void remove_edge(int vertex_a, int vertex_b) override;
	virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
	virtual vector<tuple<int,int,int>> get_edges() override;
	virtual int count_vertices() override;
};

AdjMatrix::AdjMatrix(int n) {
	for (int i = 0; i < n; i++){
		vector<int> temp;
		for (int j = 0; j < n; j++)
			temp.push_back(0);
		matrix.push_back(temp);
	}
}

void AdjMatrix::add_edge(int vertex_a, int vertex_b, int weight){
	if (matrix[vertex_a][vertex_b] != 0) return;
	matrix[vertex_a][vertex_b] = weight;
}

void AdjMatrix::remove_edge(int vertex_a, int vertex_b) {
	matrix[vertex_a][vertex_b] = 0;
}
int AdjMatrix::change_weight(int vertex_a, int vertex_b, int new_weight) {
	int old_weight = matrix[vertex_a][vertex_b];

	matrix[vertex_a][vertex_b] = new_weight;

	return old_weight;
}
void AdjMatrix::from_file(string filepath) {
	ifstream file{filepath};
	string buffer;

	// Чтение первых двух строк
	
	getline(file,buffer);
	istringstream initial_iss{buffer};
	char _type;
	initial_iss >> _type;
	int vertices;
	initial_iss >> vertices;
	for(int i = 0; i < vertices; i++) {
		matrix.push_back(vector<int>{});
		for(int j = 0; j < vertices; j++) {
			matrix[i].push_back(0);
		}
	}

	getline(file,buffer);
	
	int from_vertex = 0;
	// Чтение непосредственно данных
	while(getline(file,buffer)) {
		istringstream iss{buffer};
		int to_vertex = 0;
		int weight;
		while (iss >> weight) {
			matrix[from_vertex][to_vertex] = weight;
			to_vertex += 1;
		}
		from_vertex += 1;
	}

	file.close();
}
void AdjMatrix::to_file(string filepath,bool is_oriented, bool is_weighted) {
	ofstream file{filepath};

	file << 'C' << matrix.size() << " " << endl;
	file << (int)is_oriented << " " << (int)is_weighted << endl;
	for(int i = 0; i < matrix.size(); i++){
		for(int j = 0; j < matrix[i].size(); j++)
			file << matrix[i][j] << " ";
		file << endl;
	}
}

vector<tuple<int,int,int>> AdjMatrix::get_edges() {
	vector<tuple<int,int,int>> result;
	for(int i = 0; i < matrix.size(); i++)
		for (int j = 0; j < matrix[i].size(); j++)
			if (matrix[i][j] != 0)
				result.push_back({i,j,matrix[i][j]});
	return result;
}

int AdjMatrix::count_vertices() {
	return matrix.size();
}

// Представление в виде списка смежных вершин
class AdjList: public IGRepr {
private:
	vector<set<pair<int, int>>> list;
public:
	AdjList(int n=0);
	virtual void from_file(string filepath) override;
	virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
	virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
	virtual void remove_edge(int vertex_a, int vertex_b) override;
	virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
	virtual vector<tuple<int,int,int>> get_edges() override;
	virtual int count_vertices() override;
};

AdjList::AdjList(int n){
	for(int i = 0; i < n; i++)
		list.push_back({});
}

void AdjList::add_edge(int vertex_a, int vertex_b, int weight){
	auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
	if (found != list[vertex_a].end() && found->first == vertex_b)
		return;
	list[vertex_a].insert({vertex_b,weight});
}

void AdjList::remove_edge(int vertex_a, int vertex_b) {
	auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
	if (found == list[vertex_a].end() || found->first != vertex_b)
		return;
	list[vertex_a].erase(*found);
}
int AdjList::change_weight(int vertex_a, int vertex_b, int new_weight) {
	auto found = list[vertex_a].lower_bound({vertex_b,INT_MIN});
	int old_weight = found->second;

	list[vertex_a].erase(found);
	list[vertex_a].insert({vertex_b,new_weight});

	return old_weight;

}
void AdjList::from_file(string filepath) {
	ifstream file{filepath};
	string buffer;

	// Чтение первых двух строк

	getline(file,buffer);
	istringstream initial_iss{buffer};
	char _type;
	initial_iss >> _type;
	int vertices;
	initial_iss >> vertices;
	for(int i = 0; i < vertices; i++) {
		list.push_back(set<pair<int,int>>{});
	}

	getline(file,buffer);
	istringstream meta_iss{buffer};
	bool _oriented, weighted;
	meta_iss >> _oriented >> weighted;

	int from_vertex = 0;
	// Чтение непосредственно данных
	if (weighted) {
		while(getline(file,buffer)) {
			istringstream iss{buffer};
			int to_vertex, weight;
			while (iss >> to_vertex >> weight) {
				list[from_vertex].insert({to_vertex,weight});
			}
			from_vertex += 1;
		}
	}
	else {
		while(getline(file,buffer)) {
			istringstream iss{buffer};
			int to_vertex;
			while (iss >> to_vertex) {
				list[from_vertex].insert({to_vertex,1});
			}
			from_vertex += 1;
		}
	}
	file.close();
}
void AdjList::to_file(string filepath,bool is_oriented, bool is_weighted) {
	ofstream file{filepath};

	file << 'L' << " " << list.size() << endl;
	file << (int)is_oriented << " " << (int)is_weighted << endl;
	if (is_weighted)
		for(int i = 0; i < list.size(); i++){
			for(auto j = list[i].begin(); j != list[i].end(); ++j)
				file << j->first << " " << j-> second << " ";
			file << endl;
		}
	else
		for(int i = 0; i < list.size(); i++){
			for(auto j = list[i].begin(); j != list[i].end(); ++j)
				file << j->first << " ";
			file << endl;
		}
}

vector<tuple<int,int,int>> AdjList::get_edges() {
	vector<tuple<int,int,int>> result;
	for(int i = 0; i < list.size(); i++)
		for (auto j = list[i].begin(); j != list[i].end(); ++j)
			result.push_back({i,j->first,j->second});
	return result;
}

int AdjList::count_vertices() {
	return list.size();
}

// Представление в виде списка рёбер
class EdgeList: public IGRepr {
public:
	vector<tuple<int,int,int>> list;
	virtual void from_file(string filepath) override;
	virtual void to_file(string filepath,bool is_oriented, bool is_weighted) override;
	virtual void add_edge(int vertex_a, int vertex_b, int weight) override;
	virtual void remove_edge(int vertex_a, int vertex_b) override;
	virtual int change_weight(int vertex_a, int vertex_b, int new_weight) override;
	virtual vector<tuple<int,int,int>> get_edges() override;
	virtual int count_vertices() override;
};
void EdgeList::add_edge(int vertex_a, int vertex_b, int weight){
	auto found = find_if(list.begin(),list.end(),
		[vertex_a,vertex_b](const tuple<int,int,int>& edge) {
			return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
		}
	);
	if (found != list.end())
		return;
	list.push_back({vertex_a,vertex_b,weight});
}

void EdgeList::remove_edge(int vertex_a, int vertex_b) {
	auto found = find_if(list.begin(),list.end(),
						 [vertex_a,vertex_b](const tuple<int,int,int>& edge) {
							 return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
						 }
	);

	list.erase(found);
}
int EdgeList::change_weight(int vertex_a, int vertex_b, int new_weight) {
	auto found = find_if(list.begin(),list.end(),
						 [vertex_a,vertex_b](const tuple<int,int,int>& edge) {
							 return get<0>(edge) == vertex_a && get<1>(edge) == vertex_b;
						 }
	);
	int old_weight = get<2>(*found);

	list.erase(found);
	list.push_back({vertex_a,vertex_b,new_weight});

	return old_weight;

}
void EdgeList::from_file(string filepath) {
	ifstream file{filepath};
	string buffer;

	// Чтение первых двух строк

	getline(file,buffer);
	istringstream initial_iss{buffer};
	char _type;
	initial_iss >> _type;
	int _vertices,edges;
	initial_iss >> _vertices >> edges;
	getline(file,buffer);
	istringstream meta_iss{buffer};
	bool _oriented, weighted;
	meta_iss >> _oriented >> weighted;

	// Чтение непосредственно данных
	if (weighted) {
		while(getline(file,buffer)) {
			istringstream iss{buffer};
			int from_vertex, to_vertex, weight;
			iss >> from_vertex >> to_vertex >> weight;
			list.push_back({from_vertex,to_vertex,weight});
		}
	}
	else {
		while(getline(file,buffer)) {
			istringstream iss{buffer};
			int from_vertex, to_vertex;
			iss >> from_vertex >> to_vertex;
			list.push_back({from_vertex,to_vertex,1});
		}
	}
	file.close();
}
void EdgeList::to_file(string filepath,bool is_oriented, bool is_weighted) {
	ofstream file{filepath};

	file << 'E' << " " << count_vertices() << " " << list.size() << endl;
	file << (int)is_oriented << " " << (int)is_weighted << endl;
	if (is_weighted)
		for(auto i = list.begin(); i < list.end(); ++i){
			file << get<0>(*i) << " " << get<1>(*i) << " " << get<2>(*i) << endl;
		}
	else
		for(auto i = list.begin(); i < list.end(); ++i){
			file << get<0>(*i) << " " << get<1>(*i) << endl;
		}
}
vector<tuple<int,int,int>> EdgeList::get_edges() {
	return list;
}
int EdgeList::count_vertices() {
	int max_vertex = 0;
	for(int i = 0; i < list.size(); i++)
		max_vertex = max(max_vertex,max(get<0>(list[i]),get<1>(list[i])));
	return max_vertex + 1;
}

// Непосредственно граф
class Graph {
private:
	IGRepr* repr;
	bool oriented;
	bool weighted;
	void transformTo(IGRepr* new_repr);
public:
	void readGraph(string fileName);
	void writeGraph(string fileName);
	void addEdge(int from, int to, int weight);
	void removeEdge(int from, int to);
	int changeEdge(int from, int to, int newWeight);
	void transformToAdjList();
	void transformToAdjMatrix();
	void transformToListOfEdges();
	~Graph();
};

void Graph::readGraph(string fileName) {
	ifstream file{fileName};
	string buffer;
	getline(file,buffer);
	switch (buffer[0]) {
		case 'C':
			repr = new AdjMatrix;
			break;
		case 'E':
			repr = new EdgeList;
			break;
		case 'L':
			repr = new AdjList;
			break;
	}

	repr->from_file(fileName);
	getline(file,buffer);
	istringstream stream {buffer};
	stream >> oriented >> weighted;
	file.close();
}

void Graph::writeGraph(string fileName){
	repr->to_file(fileName,oriented,weighted);
}

void Graph::addEdge(int from, int to, int weight) {
	repr->add_edge(from, to, weight);
	if (oriented == false)
		repr->add_edge(to, from, weight);
}

void Graph::removeEdge(int from, int to) {
	repr->remove_edge(from, to);
	if (oriented == false)
		repr->remove_edge(to, from);
}
int Graph::changeEdge(int from, int to, int newWeight){
	if (weighted && newWeight != 1)
		weighted = false;
	return repr->change_weight(from, to, newWeight);
}

Graph::~Graph() {
	delete repr;
}

void Graph::transformTo(IGRepr* new_repr) {
	auto edges = repr->get_edges();
	for (int i = 0; i < edges.size(); i++)
		new_repr->add_edge(get<0>(edges[i]),get<1>(edges[i]) ,get<2>(edges[i]) );
	delete repr;
	repr = new_repr;
}
void Graph::transformToAdjList() {
	transformTo(new AdjList(repr->count_vertices()));
}
void Graph::transformToAdjMatrix(){
	transformTo(new AdjMatrix(repr->count_vertices()));
}

void Graph::transformToListOfEdges() {
	transformTo(new EdgeList);
}

int main() {
	Graph graph;
	graph.readGraph("input.txt");
	graph.transformToAdjList();
	graph.writeGraph("output_adj_list.txt");
	graph.transformToListOfEdges();
	graph.writeGraph("output_edge_list.txt");
	graph.transformToAdjMatrix();
	graph.writeGraph("output_adj_matrix.txt");

	return 0;
}