//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include using namespace std; using ll = long long; using pii = pair; using pll = pair; using pli = pair; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' #define YESNO(x) ((x) ? "Yes" : "No") #define YES YESNO(true) #define NO YESNO(false) #define REV_PRIORITY_QUEUE(tp) priority_queue,greater> #define NO_ANS(x) {cout << (x) << '\n'; return;} template void inline VEC_UNIQ(vector &v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return; } const long long B1 = 100LL; const long long B2 = 100000LL; long long md = 1002120277LL; // ロリハ // hash(S) = s[0] * B**(m-1) + s[1] * B**(m-2) + ... + s[m-1] * B**0 //色んな型に対応するようにしているが、0を入れると壊れる(一致してない列を一致していると言い張ることがある)ので注意 template class ococo_rollinghash { private: long long pb1 = 1, pb2 = 1; int n = 0; deque deq; // めんどいので雑に適当な素数にしてるが、後で(1LL << 61) - 1にして適切な高速化もやりたい static inline long long md = 1002120277LL; //const long long md = 1000000007; string s; ll hash1 = 0LL,hash2 = 0LL; ll beki(ll a,ll b){ ll ans = 1,temp = a; while(b){ if(b % 2){ ans *= temp; ans %= md; } temp *= temp; temp %= md; b /= 2; } return ans; } ll g1 = beki(B1,md - 2),g2 = beki(B2,md - 2); bool is_prime(ll x){ for(ll i = 2; i * i <= x; i++){ if(x % i == 0)return false; } return true; } public: void push_back(T c){ hash1 *= B1; hash1 += (ll)c; hash1 %= md; hash2 *= B2; hash2 += (ll)c; hash2 %= md; n++; deq.push_back((T)c % md); return; } void push_front(T c){ hash1 += beki(B1,n) * (ll)c; hash1 %= md; hash2 += beki(B2,n) * (ll)c; hash2 %= md; n++; deq.push_front((T)c % md); return; } void pop_back(void){ assert(n != 0); T c = deq.back(); deq.pop_back(); hash1 -= c; if(hash1 < 0)hash1 += md; hash1 *= g1; hash1 %= md; hash2 -= c; if(hash2 < 0)hash2 += md; hash2 *= g2; hash2 %= md; n--; return; } void pop_front(void){ assert(n != 0); T c = deq.front(); deq.pop_front(); ll temp; temp = beki(B1,n - 1) * (ll)c; temp %= md; hash1 -= temp; if(hash1 < 0)hash1 += md; temp = beki(B2,n - 1) * (ll)c; temp %= md; hash2 -= temp; if(hash2 < 0)hash2 += md; n--; return; } pll get_hash(void){ return pair(hash1,hash2); } bool empty(void){ return (n == 0); } ll change_mod(void){ random_device rd; ll val = 950000000LL + rd() % 100000000LL; while(!is_prime(val))val++; return (md = val); } }; ll beki(ll a,ll b){ b %= (md - 1); ll ans = 1,temp = a; while(b){ if(b % 2){ ans *= temp; ans %= md; } temp *= temp; temp %= md; b /= 2; } return ans; } inline ll mod_inv(ll a){ return beki(a,md - 2); } pll get_hash(vector s,vector t){ int n = (int)s.size(); //for(int i = 0; i < n; i++)cerr << s[i] << ' ' << t[i] << el; ll h1 = 0LL,h2 = 0LL; for(int i = 0; i < n; i++){ ococo_rollinghash rh; ll m = (int)s[i].size(); for(int j = 0; j < (int)m; j++){ rh.push_back(s[i][j]); } ll th1,th2; tie(th1,th2) = rh.get_hash(); //cerr << th1 << ' ' << th2 << el; th1 *= (beki(B1,m * (t[i] % (md - 1))) - 1LL); th1 %= md; th1 *= mod_inv(beki(B1,m) - 1); th1 %= md; th2 *= (beki(B2,m * (t[i] % (md - 1))) - 1LL); th2 %= md; th2 *= mod_inv(beki(B2,m) - 1); th2 %= md; //cerr << m * (t[i] % (md - 1)) << el; h1 *= beki(B1,(m * (t[i] % (md - 1)))); h1 += th1; h1 %= md; h2 *= beki(B2,(m * (t[i] % (md - 1)))); h2 += th2; h2 %= md; //cerr << h1 << ' ' << h2 << el; } return pair(h1,h2); } #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く //複数の解法のアイデアを思いついた時は全部メモしておく //g++ -D_GLIBCXX_DEBUG -Wall -Wextra -O2 i.cpp -o o int k; cin >> k; ococo_rollinghash temp; md = temp.change_mod(); //cerr << md << el; vector s(k),revs(k); vector t(k),revt(k); for(int i = 0; i < k; i++){ cin >> s[i] >> t[i]; revs[i] = s[i]; revt[i] = t[i]; reverse(revs[i].begin(),revs[i].end()); } reverse(revs.begin(),revs.end()); reverse(revt.begin(),revt.end()); /* for(int i = 0; i < k; i++){ cerr << s[i] << ' ' << t[i] << el; } for(int i = 0; i < k; i++){ cerr << revs[i] << ' ' << revt[i] << el; } */ cout << YESNO(get_hash(s,t) == get_hash(revs,revt)) << el; return; } void calc(void){ return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }