#include <gmpxx.h>
#include <iostream>
#include <vector>
#include <queue>
#include "validation.h"

using namespace std;

// Invert a given matrix, specified in row-major order. Throws exception when
// input is not a square matrix or is not invertible.
//
// The algorithm below is based on the following idea: Let U be the input
// matrix, and assume it is invertible. Then U U^{-1} = 1. If we were to find
// some series of matrices A_1, ... , A_n such that A_n A_{n-1} ... A_1 U = 1,
// then U^{-1} = A_n A_{n-1} ... A_1
//
// The code below uses three basic operations:
//  - Swapping two rows
//  - Multiplying a row by a non-zero rational
//  - Adding a multiple of one row to another
// all of which can be represented as invertable matrices, to find a sequence
// of operations that reduce U to the identity. It simultaneously applies the
// same sequence to an identiy matrix to construct U^{-1}.
//
// It does this in two steps:
//  - First, it reduces U to an upper triangular form, with only 1s on the
//    diagonal. (It is trivial to see this is always possible for invertible
//    matrices, as the identiy matrix satisfies this requirement)
//  - Second, it goes back through the matrix to eliminate all off-diagonal
//    non-zero elements.
// After these steps, the output matrix will contain the inverse of the input
// matrix.
//
// Complexity: O(N^3), where N is the number of rows (equivalently: colums) in
// the matrix.
vector<vector<mpq_class>> MatrixInverse(vector<vector<mpq_class>> in) {
	// Check that the input is indeed a square matrix
	size_t N = in.size();
	if (N < 1)
		throw "No input";
	for (size_t i=0; i<N; i++) {
		if (in[i].size() != N)
			throw "Input size wrong";
	}
	
	// Setup output matrix as identity
	vector<vector<mpq_class>> out(N, vector<mpq_class>(N, 0_mpq));
	for (size_t i=0; i<N; i++) {
		out[i][i] = 1_mpq;
	}
	
	// Transform input matrix into upper triangular form
	for (size_t i=0; i<N; i++) {
		// Find the index of the first row (with index >= i) with a non-zero value
		// in column i
		size_t j;
		for (j=i; j<N; j++) {
			if (in[j][i] != 0_mpq)
				break;
		}
		if (j == N)
			throw "Matrix not invertible";
		
		// Swap rows into position if needed
		if (i != j) {
			in[i].swap(in[j]);
			out[i].swap(out[j]);
		}
		
		// Rescale row such that in[i][i] becomes 1
		mpq_class S = in[i][i];
		for (size_t k = 0; k<N; k++) {
			in[i][k] /= S;
			out[i][k] /= S;
		}
		
		// Sweep to ensure rest of column becomes zero
		for (size_t k=i+1; k<N; k++) {
			mpq_class S = in[k][i];
			for (size_t l=0; l<N; l++) {
				in[k][l] -= S*in[i][l];
				out[k][l] -= S*out[i][l];
			}
		}
	}
	
	// Sweep back up to reach identity matrix in in[][]
	for (size_t i=N-1; i>0; i--) { // row 0 wont sweep out anything so this is ok
		for (size_t j=0; j<i; j++) {
			mpq_class S = in[j][i];
			for (size_t l=0; l<N; l++) {
				in[j][l] -= S*in[i][l];
				out[j][l] -= S*out[i][l];
			}
		}
	}
	
	return out;
}

// Calculate the output ratio of a configuration of splitters.
//
// This function formulates a set of equations of form
// x_i = \sum a_{i,j}*x_j + \delta_{i,0}
// where each x_i represents the input of the ith splitter (letting x_{-1} and
// x_{-2} be the outputs).
//
// It then uses matrix inversion to solve the system and derive the ratio
// of outputs. Returns 0 0 as output ratios if the configuration has no
// solution, or no unique solution.
pair<mpq_class, mpq_class> CalculateRatio(vector<pair<int, int>> configuration, 
                                          int c, int d) {
	size_t N = configuration.size() + 2;
	if (N == 2) {
		// No splitters, so no output
		return make_pair(0_mpq, 0_mpq);
	}
	
	// Rewrite c and d into fractions
	mpq_class Crat(c, c+d), Drat(d, c+d);
	Crat.canonicalize(); // Required since we don't know whether c and d
	Drat.canonicalize(); // share a factor
	
	// Write equations in matrix form, shifting indices up 2 so -1 and -2
	// become >= 0.
	vector<vector<mpq_class>> equations(N, vector<mpq_class>(N, 0_mpq));
	for (size_t i=0; i<N; i++) {
		// Setup diagonal
		equations[i][i] = -1;
	}
	for (size_t i=0; i<configuration.size(); i++) {
		// Add outputs of splitter to specified inputs.
		equations[configuration[i].first+2][i+2] += Crat;
		equations[configuration[i].second+2][i+2] += Drat;
	}
	
	// Solve the problem by inverting the matrix, then the answer will be in
	// elements -A^{-1}_1,2 and -A^{-1}_0,2
	try {
		auto inverse = MatrixInverse(equations);
		return make_pair(-inverse[1][2], -inverse[0][2]);
	} catch (const char *e) {
		// System was not solvable, so wrong answer with 0 0
		return make_pair(0_mpq, 0_mpq);
	}
}

// Debugging utility (useful in gdb to print matrices, as mpqs dont print
// nicely otherwise)
void dumpMatrix(vector<vector<mpq_class>> in) {
	for (auto v : in) {
		for (auto u : v) {
			cout << u << " ";
		}
		cout << endl;
	}
}

// Main is responsible for parsing the user output and doing the actual check that ratios are reasonable.
int main(int argc, char **argv) {
	// Set up the input and answer streams.
	std::ifstream in(argv[1]);    // testcase input
	OutputValidator v(argc, argv); // team output

	// read problem statement parameters a, b, c and d
	int a,b,c,d;
	in >> a >> b >> c >> d;

	// read user solution
	int n = v.read_int(1,200);
	v.newline();
	vector<pair<int, int>> configuration(n);
	for (int i=0; i<n; i++) {
		configuration[i].first = v.read_int(-2, n-1);
		v.space();
		configuration[i].second = v.read_int(-2, n-1);
		v.newline();
	}
	
	// Check reachability
	vector<bool> reach(n, false);
	queue<int> work;
	reach[0] = true;
	work.push(0);
	while (!work.empty()) {
		int cur = work.front();
		work.pop();
		
		if (configuration[cur].first >= 0) {
			if (!reach[configuration[cur].first]) {
				reach[configuration[cur].first] = true;
				work.push(configuration[cur].first);
			}
		}
		if (configuration[cur].second >= 0) {
			if (!reach[configuration[cur].second]) {
				reach[configuration[cur].second] = true;
				work.push(configuration[cur].second);
			}
		}
	}
	
	for (int i=0; i<n; i++) {
		if (!reach[i])
			v.WA("Unreachable splitter");
	}

	// Validate solution
	mpq_class Tc(c,c+d), Td(d, c+d);
	Tc.canonicalize();
	Td.canonicalize();
	auto ratio = CalculateRatio(configuration, a, b);
	if (ratio.first != Tc || ratio.second != Td)
		v.WA("Output produces incorrect ratio: wanted ", Tc , " but found ", ratio.first);
	
	return 0;
}