#include #include #include #include using namespace std; template class Trie { struct Node { const uint32_t from, letter; uint32_t count_as_prefix = 0; uint32_t count_as_same = 0; array next_as = { }; constexpr Node(const uint32_t from, const uint32_t letter) noexcept : from(from), letter(letter) { } }; protected: vector nodes; constexpr void disable_all_below(const uint32_t index) noexcept { nodes[index].count_as_prefix = nodes[index].count_as_same = 0; for (uint32_t i = 0; i != letter_kinds; ++i) if (nodes[index].next_as[i] != 0) disable_all_below(nodes[index].next_as[i]); } public: constexpr Trie() : nodes(1, Node(0, UINT32_MAX)) { } constexpr Trie(const uint32_t reservation) : nodes(1, Node(0, UINT32_MAX)) { nodes.reserve(reservation); } constexpr const Node& operator[](const uint32_t index) const noexcept { return nodes[index]; } constexpr uint32_t index_of(const string& S, const bool phantom_mode = false) noexcept { uint32_t cur = 0; for (uint32_t i = 0; i != S.size(); ++i) if ((cur = nodes[cur].next_as[S[i] - base]) == 0) return UINT32_MAX; if (phantom_mode || nodes[cur].count_as_prefix != 0) return cur; else return UINT32_MAX; } constexpr void add_word(const string& S) noexcept { uint32_t cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { ++nodes[cur].count_as_prefix; if (nodes[cur].next_as[S[i] - base] == 0) nodes[cur].next_as[S[i] - base] = nodes.size(), nodes.emplace_back(cur, S[i] - base); cur = nodes[cur].next_as[S[i] - base]; } ++nodes[cur].count_as_prefix, ++nodes[cur].count_as_same; } constexpr uint32_t remove_word(const string& S, const bool all_remove_mode = true) noexcept { const uint32_t remove_count = all_remove_mode ? count_word(S) : 1; if (remove_count == 0 || (all_remove_mode && count_word(S) == 0)) return 0; uint32_t cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { nodes[cur].count_as_prefix -= remove_count; cur = nodes[cur].next_as[S[i] - base]; } nodes[cur].count_as_prefix -= remove_count; nodes[cur].count_as_same -= remove_count; return remove_count; } constexpr uint32_t remove_prefix(const string& prefix) noexcept { const uint32_t remove_count = count_prefix(prefix); if (remove_count == 0) return 0; uint32_t cur = 0; for (uint32_t i = 0; i != prefix.size(); ++i) { nodes[cur].count_as_prefix -= remove_count; cur = nodes[cur].next_as[prefix[i] - base]; } disable_all_below(cur); return remove_count; } constexpr uint32_t remove_prefix_of(const string& S) noexcept { uint32_t remove_count = 0, cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { remove_count += nodes[cur].count_as_same; nodes[cur].count_as_prefix -= nodes[cur].count_as_same; nodes[cur].count_as_same = 0; cur = nodes[cur].next_as[S[i] - base]; } return remove_count; } constexpr uint32_t count_word(const string& S) const noexcept { uint32_t cur = 0; for (uint32_t i = 0; i != S.size(); ++i) if ((cur = nodes[cur].next_as[S[i] - base]) == 0) return 0; return nodes[cur].count_as_same; } constexpr uint32_t count_prefix(const string& prefix) const noexcept { uint32_t cur = 0; for (uint32_t i = 0; i != prefix.size(); ++i) if ((cur = nodes[cur].next_as[prefix[i] - base]) == 0) return 0; return nodes[cur].count_as_prefix; } constexpr uint32_t count_prefix_of(const string& S) const noexcept { uint32_t count = 0, cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { count += nodes[cur].count_as_same; if ((cur = nodes[cur].next_as[S[i] - base]) == 0) return count; } return count += nodes[cur].count_as_same; } constexpr uint32_t count_until(const string& S) const noexcept { uint32_t count = 0, cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { for (uint32_t j = 0; j != (S[i] - base); ++j) if (nodes[cur].next_as[j] != 0) count += nodes[nodes[cur].next_as[j]].count_as_prefix; if ((cur = nodes[cur].next_as[S[i] - base]) == 0) return count; } return count += nodes[cur].count_as_same; } constexpr uint32_t count_after(const string& S) const noexcept { uint32_t count = 0, cur = 0; for (uint32_t i = 0; i != S.size(); ++i) { for (uint32_t j = letter_kinds - 1; j != (S[i] - base); --j) if (nodes[cur].next_as[j] != 0) count += nodes[nodes[cur].next_as[j]].count_as_prefix; if ((cur = nodes[cur].next_as[S[i] - base]) == 0) return count; } return count += nodes[cur].count_as_prefix - nodes[cur].count_as_same; } constexpr string search_kth_word(const uint32_t index) const noexcept { uint32_t count = 0, cur = 0; string result = ""s; if ((count += nodes[cur].count_as_prefix) <= index) return ""s; while (1) { uint32_t i = letter_kinds; while (--i != UINT32_MAX) { if (nodes[cur].next_as[i] != 0) continue; if (count <= index + nodes[nodes[cur].next_as[i]].count_as_prefix) { result += base + i; cur = nodes[cur].next_as[i]; break; } else count -= nodes[nodes[cur].next_as[i]].count_as_prefix; } if (i == UINT32_MAX) return result; } } constexpr void reserve(const uint32_t reservation) { nodes.reserve(reservation); } constexpr uint32_t size() const noexcept { return nodes[0].count_as_prefix; } }; static inline constexpr const char* solve(const uint_fast32_t N, const vector& S, const vector& T) noexcept { Trie names(15 * N); for (uint_fast32_t i = 0; i != N; ++i) names.add_word(S[i]), names.add_word(T[i]); for (uint_fast32_t i = 0; i != N; ++i) if (names.count_word(S[i]) > 1 && names.count_word(T[i]) > 1) return "No"; return "Yes"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t N, i; std::cin >> N; vector S(N), T(N); for (i = 0; i != N; ++i) { S[i].reserve(15), T[i].reserve(15); cin >> S[i] >> T[i]; } std::cout << solve(N, S, T) << '\n'; return 0; }