#include #include #include #include using namespace std; typedef map IndexTable; struct Rate { int nom; int denom; Rate(): nom(0), denom(0) {} Rate(int n, int d): nom(n), denom(d) { int dv = gcd(nom, denom); nom /= dv; denom /= dv; } bool valid() const { return nom && denom; } Rate reverse() const { return Rate(denom, nom); } bool operator==(const Rate& r) const { return nom*r.denom == denom*r.nom; } bool operator!=(const Rate& r) const { return !(*this == r); } bool operator>(const Rate& r) const { return nom*r.denom > denom*r.nom; } bool operator<(const Rate& r) const { return nom*r.denom < denom*r.nom; } friend istream& operator>>(istream& is, Rate& r) { char delim; return is >> r.nom >> delim >> r.denom; } friend ostream& operator<<(ostream& os, const Rate& r) { return os << r.nom << ":" << r.denom; } Rate operator*(const Rate& r) const { return Rate(nom*r.nom, denom*r.denom); } Rate operator/(int d) const { return Rate(nom/d, denom/d); } static int gcd(int A, int B) { if (B > A) { int tmp = A; A = B; B = tmp; } int r = A / B; int m = A - r * B; while (m) { A = B; B = m; r = A / B; m = A - r * B; } return B; } }; typedef vector XchgTable; int main(int argc, char* argv[]) { int C; while (cin >> C) { if (!C) break; string str; IndexTable index; XchgTable table; table.resize(C*C, Rate()); for (int i=0; i> str; index[str] = i; table[i+i*C] = Rate(1, 1); } int R; cin >> R; for (int i=0; i> str; int iA = index[str]; cin >> str; int iB = index[str]; cin >> table[iB+iA*C]; } bool cycle = true; while (cycle) { cycle = false; for (int y=0; y