#include "validation.h"
#include <stack>
#include <vector>

// Check the correctness of the answer here.
// Your program must return 42 when the input is correct.
// When there is something wrong with the input, return 43.
// In this case, it is also a good idea to print some useful debug information to stdout.

// When your program crashes unexpectedly, or something weird is going on,
// please write some info to stderr and return anything different from 42 and 43.

// called as:
// output_validator input answer feedbackdir < output

struct BCC { // find AVs and bridges in an undirected graph
	vector<vector<int>> &edges;
	int V, counter = 0, root; // root and # children of root
	vector<int> n, l;         // nodes,low
	stack<int> s;
	int components = 0;
	BCC(vector<vector<int>> &e) : edges(e), V(e.size()), n(V, -1), l(V, -1) {}
	vector<pair<int,int>> bridges;
	void visit(int u, int p) { // also pass the parent
		l[u] = n[u] = counter++;
		s.push(u);
		bool skipped_parent = false;
		for(auto &v : edges[u]) {
			if(n[v] == -1) {
				visit(v, u);
				if(l[v] > n[u]) {
					// u->v is a bridge
					bridges.push_back({u,v});
					++components;
					while(true) { // biconnected component
						int w = s.top();
						s.pop(); // <= ACT HERE
						if(w == v) break;
					}
				}
				l[u] = min(l[u], l[v]);
			} else if(skipped_parent || v != p) {
				l[u] = min(l[u], n[v]);
			} else { // v==p
				skipped_parent = true;
			}
		}
	}
	int run() {
		for(int u = 0; u < V; ++u)
			if(n[u] == -1) {
				root = u;
				visit(u, -1);
				if(!s.empty()) {
					++components;
					s = stack<int>();
				}
			}
		return components;
	}
};

int main(int argc, char **argv) {
	std::ifstream in(argv[1]);
	std::ifstream ans(argv[2]);

	int optimal_ans;
	ans >> optimal_ans;

	// Validate the team output.
	OutputValidator out(argc, argv);
	int m = out.read_long_long(optimal_ans, optimal_ans);
	out.newline();

	// Build the tree.
	int n, power_source;
	in >> n >> power_source;
	vector<vector<int>> tree(n);

	// Read input edges.
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		in >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	// Read additional edges.
	for(int i = 0; i < m; ++i) {
		int u = out.read_long_long(0, n - 1);
		out.space();
		int v = out.read_long_long(0, n - 1);
		out.newline();
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	// Check that the tree is biconnected.
	BCC bcc(tree);
	int components = bcc.run();
	if(components != 1){
		out.WA("The graph has ", components, " biconnected components, not 1.", "\nFound bridge: ", bcc.bridges[0].first, "-", bcc.bridges[0].second);
	}
}