#include "validation.h"
#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.

// For default output validation, where the team output is directly compared to the .ans,
// this script is called as:
//		output_validator input answer feedbackdir < answer
//
// Please validate:
//	- the syntax/grammer of the answer file.
//	- optionally, the correctness of the answer.

// For custom output validation, this is called as:
//		output_validator input answer feedbackdir < team_output
//
// Please validate:
//	- The syntax/grammar of the team output.
//	- The correctness of the team output.

struct UnionFind {
	vector<int> par, rank;
	int c;
	UnionFind(int n) : par(n), rank(n, 0), c(n) {
		for(int i = 0; i < n; ++i) par[i] = i;
	}
	int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); }
	int count() { return c; }
	void merge(int i, int j) {
		if((i = find(i)) == (j = find(j))) return;
		c--;
		if(rank[i] > rank[j]) swap(i, j);
		par[i] = j;
		if(rank[i] == rank[j]) rank[j]++;
	}
};

// 1) Check the team printed the right weight.
// 2) Check that the team output is a tree.
// 3) Check that its weight equals the answer weight.
int main(int argc, char **argv) {
	// Set up the input and answer streams.
	std::ifstream in(argv[1]);
	std::ifstream ans(argv[2]);
	Validator out(argc, argv, cin);

	int n, k;
	in >> n >> k;
	vector<string> dna(n);
	for(auto &x : dna) in >> x;

	// 1) right weight?
	int answer;
	ans >> answer;

	int team_answer = out.read_long_long(answer, answer);
	out.newline();

	// 2) tree?
	int weight = 0;
	UnionFind uf(n);
	for(int i = 0; i < n - 1; ++i) {
		int u = out.read_long_long(0, n - 1);
		out.space();
		int v = out.read_long_long(0, n - 1);
		out.newline();

		uf.merge(u, v);

		for(int j = 0; j < k; ++j)
			if(dna[u][j] != dna[v][j]) ++weight;
	}

	if(uf.count() != 1)
		out.WA("The given edges do not form a tree. Expected 1 component, got", uf.count());

	if(weight != answer) out.WA("weight of ", weight, " does not equal answer of ", answer);
}