func_code_string: #include <bits/stdc++.h>   using namespace std;   long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }   const int MAXN = 58;   const int MAXQ = 5000;   int n;   int bto[MAXN - 1], rto[MAXN - 1];   int nq;   int qat[MAXQ];   char qlast[MAXQ][MAXN - 1 + 1];   long long qans[MAXQ];   int dr[MAXN - 1];   void mlt64(unsigned long long x, unsigned long long y, unsigned long long& hi,              unsigned long long& lo) {     unsigned long long xhi = x >> 32, xlo = x & ((1ULL << 32) - 1), yhi = y >> 32,                        ylo = y & ((1ULL << 32) - 1);     unsigned long long zlo = xlo * ylo, tmp = xhi * ylo + (zlo >> 32),                        zmi = tmp & ((1ULL << 32) - 1), zhi = tmp >> 32;     zmi += xlo * yhi, zhi += xhi * yhi;     lo = (zlo & (1ULL << 32) - 1) + ((zmi & (1ULL << 32) - 1) << 32),     hi = zhi + (zmi >> 32);   }   template <int k>   struct MersenneMod64bit {     constexpr static unsigned long long mod() { return (1ULL << k) - 1; }     unsigned long long val;     MersenneMod64bit() { val = 0; }     MersenneMod64bit(unsigned long long _val) {       val = (_val & mod()) + (_val >> k);       if (val >= mod()) val -= mod();     }     const unsigned long long operator()() const { return val; }     MersenneMod64bit& operator+=(const MersenneMod64bit& other) {       val += other.val;       if (val >= mod()) val -= mod();       return *this;     }     MersenneMod64bit& operator-=(const MersenneMod64bit& other) {       if (val >= other.val)         val -= other.val;       else         val += mod() - other.val;       return *this;     }     MersenneMod64bit& operator*=(const MersenneMod64bit& other) {       unsigned long long hi, lo;       mlt64(val, other.val, hi, lo);       val = (lo & mod()) + (lo >> k) + (hi << (64 - k));       if (val >= mod()) val -= mod();       return *this;     }     MersenneMod64bit& operator/=(const MersenneMod64bit& other) {       return *this *= other.inverse();     }     MersenneMod64bit operator*(const MersenneMod64bit& other) const {       return MersenneMod64bit(*this) *= other;     }     bool operator==(const MersenneMod64bit& other) { return val == other.val; }     bool operator!=(const MersenneMod64bit& other) { return val != other.val; }     MersenneMod64bit pw(unsigned long long n) const {       MersenneMod64bit ret = 1, x = *this;       while (true) {         if (n & 1) ret *= x;         if ((n >>= 1) == 0) return ret;         x *= x;       }     }     MersenneMod64bit inverse() const { return pw(mod() - 2); }   };   template <int k>   ostream& operator<<(ostream& stream, const MersenneMod64bit<k>& number) {     return stream << number();   }   template <typename T>   struct Matrix {     int n, m;     vector<vector<T>> A;     Matrix(int n) : n(n), m(n) { A = vector<vector<T>>(n, vector<T>(m, 0)); }     Matrix(int n, int m) : n(n), m(m) {       A = vector<vector<T>>(n, vector<T>(m, 0));     }     vector<T>& operator[](int i) { return A[i]; }     void gaussjord() {       int R = n, C = m, r = 0, c = 0;       while (r < R && c < C) {         {           int rr = r;           while (rr < R && A[rr][c] == 0) ++r;           if (rr >= R) {             ++c;             continue;           }           if (rr != r)             for (int cc = (c); cc < (C); ++cc) swap(A[r][cc], A[rr][cc]);         }         if (A[r][c] != 1) {           T x = 1;           x /= A[r][c];           for (int cc = (c + 1); cc < (C); ++cc) A[r][cc] *= x;           A[r][c] = 1;         }         for (int rr = (0); rr < (R); ++rr)           if (rr != r && A[rr][c] != 0) {             for (int cc = (c + 1); cc < (C); ++cc)               A[rr][cc] -= A[rr][c] * A[r][cc];             A[rr][c] = 0;           }         ++r, ++c;       }     }     Matrix inverse() {       assert(n == m);       Matrix B(n, 2 * n);       for (int i = (0); i < (n); ++i)         for (int j = (0); j < (n); ++j)           B[i][j] = A[i][j], B[i][n + j] = i == j ? 1 : 0;       B.gaussjord();       for (int i = (0); i < (n); ++i) assert(B[i][i] == 1);       Matrix ret(n);       for (int i = (0); i < (n); ++i)         for (int j = (0); j < (n); ++j) ret[i][j] = B[i][n + j];       return ret;     }     Matrix operator*(const Matrix& other) const {       assert(m == other.n);       Matrix ret(n, other.m);       for (int i = (0); i < (n); ++i)         for (int j = (0); j < (other.m); ++j)           for (int k = (0); k < (m); ++k) ret[i][j] += A[i][k] * other.A[k][j];       return ret;     }     vector<T> operator*(const vector<T>& vec) const {       assert(m == ((int)(vec).size()));       vector<T> ret(n, 0);       for (int i = (0); i < (n); ++i)         for (int k = (0); k < (m); ++k) ret[i] += A[i][k] * vec[k];       return ret;     }     void print() {       for (int i = (0); i < (n); ++i) {         for (int j = (0); j < (m); ++j) {           if (j != 0) cout <<    ;           cout << A[i][j];         }         cout <<   n ;       }     }   };   using M61 = MersenneMod64bit<61>;   using Mat = Matrix<M61>;   using Vec = vector<M61>;   bool dec(unsigned long long& a, unsigned long long b) {     if (a < b) return false;     a -= b;     return true;   }   bool solveslinearequation(int q, const Vec& x) {     for (int i = (0); i < (n - 1); ++i) dr[i] = qlast[q][i] ==  B  ? 0 : 1;     bool ok = true;     vector<unsigned long long> bal(n, 0);     for (int i = (0); i < (n - 1); ++i) bal[i] += 2 * x[i]() + dr[i];     ++bal[qat[q]];     for (int i = (0); i < (n - 1); ++i) {       ok = ok && dec(bal[bto[i]], x[i]());       ok = ok && dec(bal[rto[i]], x[i]() + dr[i]);     }     ok = ok && dec(bal[0], 1);     for (int i = (0); i < (n); ++i) ok = ok && bal[i] == 0;     return ok;   }   bool visitedstatesgotodestination(int q, const Vec& x) {     for (int i = (0); i < (n - 1); ++i) dr[i] = qlast[q][i] ==  B  ? 0 : 1;     vector<bool> visited(n - 1);     for (int i = (0); i < (n - 1); ++i) visited[i] = x[i]() > 0 || dr[i] > 0;     vector<vector<int>> radj(n);     for (int i = (0); i < (n); ++i)       if (qlast[q][i] ==  B )         radj[bto[i]].push_back(i);       else         radj[rto[i]].push_back(i);     queue<int> queue;     vector<bool> todest(n, false);     todest[qat[q]] = true, queue.push(qat[q]);     while (!queue.empty()) {       int at = queue.front();       queue.pop();       for (int i = (0); i < (((int)(radj[at]).size())); ++i) {         int to = radj[at][i];         if (!todest[to]) todest[to] = true, queue.push(to);       }     }     for (int i = (0); i < (n); ++i)       if (visited[i] && !todest[i]) return false;     return true;   }   void solve() {     Mat A(n - 1);     for (int i = (0); i < (n - 1); ++i) {       A[i][i] -= 2;       if (bto[i] != n - 1) A[bto[i]][i] += 1;       if (rto[i] != n - 1) A[rto[i]][i] += 1;     }     Mat Ainv = A.inverse();     for (int q = (0); q < (nq); ++q) {       for (int i = (0); i < (n - 1); ++i) dr[i] = qlast[q][i] ==  B  ? 0 : 1;       Vec y(n - 1);       y[0] -= 1;       y[qat[q]] += 1;       for (int i = (0); i < (n - 1); ++i) {         y[i] += dr[i];         if (rto[i] != n - 1) y[rto[i]] -= dr[i];       }       Vec x = Ainv * y;       bool ok = solveslinearequation(q, x) && visitedstatesgotodestination(q, x);       if (!ok)         qans[q] = -1;       else {         qans[q] = 0;         for (int i = (0); i < (n - 1); ++i) qans[q] += 2 * x[i]() + dr[i];       }     }   }   void run() {     scanf( %d , &n);     for (int i = (0); i < (n - 1); ++i)       scanf( %d%d , &bto[i], &rto[i]), --bto[i], --rto[i];     scanf( %d , &nq);     for (int i = (0); i < (nq); ++i) scanf( %d%s , &qat[i], qlast[i]), --qat[i];     solve();     for (int i = (0); i < (nq); ++i) printf( %lld n , qans[i]);   }   int main() {     run();     return 0;   }   