#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC optimize("Ofast") //#undef LOCAL #include #include #include #include #include #include namespace atcoder { namespace internal { template struct simple_queue { std::vector payload; int pos = 0; void reserve(int n) { payload.reserve(n); } int size() const { return int(payload.size()) - pos; } bool empty() const { return pos == int(payload.size()); } void push(const T& t) { payload.push_back(t); } T& front() { return payload[pos]; } void clear() { payload.clear(); pos = 0; } void pop() { pos++; } }; } // namespace internal } // namespace atcoder namespace atcoder { template struct mf_graph { public: mf_graph() : _n(0) {} explicit mf_graph(int n) : _n(n), g(n) {} int add_edge(int from, int to, Cap cap) { assert(0 <= from && from < _n); assert(0 <= to && to < _n); assert(0 <= cap); int m = int(pos.size()); pos.push_back({from, int(g[from].size())}); int from_id = int(g[from].size()); int to_id = int(g[to].size()); if (from == to) to_id++; g[from].push_back(_edge{to, to_id, cap}); g[to].push_back(_edge{from, from_id, 0}); return m; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { int m = int(pos.size()); assert(0 <= i && i < m); auto _e = g[pos[i].first][pos[i].second]; auto _re = g[_e.to][_e.rev]; return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap}; } std::vector edges() { int m = int(pos.size()); std::vector result; for (int i = 0; i < m; i++) { result.push_back(get_edge(i)); } return result; } void change_edge(int i, Cap new_cap, Cap new_flow) { int m = int(pos.size()); assert(0 <= i && i < m); assert(0 <= new_flow && new_flow <= new_cap); auto& _e = g[pos[i].first][pos[i].second]; auto& _re = g[_e.to][_e.rev]; _e.cap = new_cap - new_flow; _re.cap = new_flow; } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < _n); assert(0 <= t && t < _n); assert(s != t); std::vector level(_n), iter(_n); internal::simple_queue que; auto bfs = [&]() { std::fill(level.begin(), level.end(), -1); level[s] = 0; que.clear(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto e : g[v]) { if (e.cap == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; int level_v = level[v]; for (int& i = iter[v]; i < int(g[v].size()); i++) { _edge& e = g[v][i]; if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][e.rev].cap)); if (d <= 0) continue; g[v][i].cap += d; g[e.to][e.rev].cap -= d; res += d; if (res == up) return res; } level[v] = _n; return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(iter.begin(), iter.end(), 0); Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } return flow; } std::vector min_cut(int s) { std::vector visited(_n); internal::simple_queue que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto e : g[p]) { if (e.cap && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } private: int _n; struct _edge { int to, rev; Cap cap; }; std::vector> pos; std::vector> g; }; } // namespace atcoder #include #include #include #include #include #include #include #include #include #include namespace yosupo { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } } // namespace internal int bsf(unsigned int n) { return __builtin_ctz(n); } int bsf(unsigned long n) { return __builtin_ctzl(n); } int bsf(unsigned long long n) { return __builtin_ctzll(n); } int bsf(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return low ? __builtin_ctzll(low) : 64 + __builtin_ctzll(high); } int bsr(unsigned int n) { return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n); } int bsr(unsigned long n) { return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n); } int bsr(unsigned long long n) { return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n); } int bsr(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low); } int popcnt(unsigned int n) { return __builtin_popcount(n); } int popcnt(unsigned long n) { return __builtin_popcountl(n); } int popcnt(unsigned long long n) { return __builtin_popcountll(n); } } // namespace yosupo #include #include #include namespace yosupo { namespace internal { template using is_signed_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using is_integral = typename std::conditional::value || internal::is_signed_int128::value || internal::is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed_int = typename std::conditional<(is_integral::value && std::is_signed::value) || is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned_int = typename std::conditional<(is_integral::value && std::is_unsigned::value) || is_unsigned_int128::value, std::true_type, std::false_type>::type; template using to_unsigned = typename std::conditional< is_signed_int128::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; template using is_integral_t = std::enable_if_t::value>; template using is_signed_int_t = std::enable_if_t::value>; template using is_unsigned_int_t = std::enable_if_t::value>; template using to_unsigned_t = typename to_unsigned::type; } // namespace internal } // namespace yosupo namespace yosupo { struct Scanner { public: Scanner(const Scanner&) = delete; Scanner& operator=(const Scanner&) = delete; Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; } void read() {} template void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } int read_unsafe() { return 0; } template int read_unsafe(H& h, T&... t) { bool f = read_single(h); if (!f) return 0; return 1 + read_unsafe(t...); } int close() { return ::close(fd); } private: static constexpr int SIZE = 1 << 15; int fd = -1; std::array line; int st = 0, ed = 0; bool eof = false; bool read_single(std::string& ref) { if (!skip_space()) return false; ref = ""; while (true) { char c = top(); if (c <= ' ') break; ref += c; st++; } return true; } bool read_single(double& ref) { std::string s; if (!read_single(s)) return false; ref = std::stod(s); return true; } template ::value>* = nullptr> bool read_single(T& ref) { if (!skip_space<50>()) return false; ref = top(); st++; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(T& sref) { using U = internal::to_unsigned_t; if (!skip_space<50>()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } U ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); sref = neg ? -ref : ref; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(U& ref) { if (!skip_space<50>()) return false; ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); return true; } bool reread() { if (ed - st >= 50) return true; if (st > SIZE / 2) { std::memmove(line.data(), line.data() + st, ed - st); ed -= st; st = 0; } if (eof) return false; auto u = ::read(fd, line.data() + ed, SIZE - ed); if (u == 0) { eof = true; line[ed] = '\0'; u = 1; } ed += int(u); line[ed] = char(127); return true; } char top() { if (st == ed) { bool f = reread(); assert(f); } return line[st]; } template bool skip_space() { while (true) { while (line[st] <= ' ') st++; if (ed - st > TOKEN_LEN) return true; if (st > ed) st = ed; for (auto i = st; i < ed; i++) { if (line[i] <= ' ') return true; } if (!reread()) return false; } } }; struct Printer { public: template void write() {} template void write(const H& h, const T&... t) { if (F) write_single(sep); write_single(h); write(t...); } template void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fd(fileno(_fp)) {} ~Printer() { flush(); } int close() { flush(); return ::close(fd); } void flush() { if (pos) { auto res = ::write(fd, line.data(), pos); assert(res != -1); pos = 0; } } private: static std::array, 100> small; static std::array tens; static constexpr size_t SIZE = 1 << 15; int fd; std::array line; size_t pos = 0; std::stringstream ss; template ::value>* = nullptr> void write_single(const T& val) { if (pos == SIZE) flush(); line[pos++] = val; } template * = nullptr, std::enable_if_t::value>* = nullptr> void write_single(const T& val) { using U = internal::to_unsigned_t; if (val == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); U uval = val; if (val < 0) { write_single('-'); uval = -uval; } write_unsigned(uval); } template * = nullptr> void write_single(U uval) { if (uval == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); write_unsigned(uval); } template * = nullptr> static int calc_len(U x) { int i = (bsr(x) * 3 + 3) / 10; if (x < tens[i]) return i; else return i + 1; } template * = nullptr, std::enable_if_t<2 >= sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template * = nullptr, std::enable_if_t<4 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { std::array buf; memcpy(buf.data() + 6, small[uval % 100].data(), 2); memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2); memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2); memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2); if (uval >= 100000000) { if (uval >= 1000000000) { memcpy(line.data() + pos, small[uval / 100000000 % 100].data(), 2); pos += 2; } else { line[pos] = char('0' + uval / 100000000); pos++; } memcpy(line.data() + pos, buf.data(), 8); pos += 8; } else { size_t len = calc_len(uval); memcpy(line.data() + pos, buf.data() + (8 - len), len); pos += len; } } template * = nullptr, std::enable_if_t<8 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template < class U, std::enable_if_t::value>* = nullptr> void write_unsigned(U uval) { static std::array buf; size_t len = 0; while (uval > 0) { buf[len++] = char((uval % 10) + '0'); uval /= 10; } std::reverse(buf.begin(), buf.begin() + len); memcpy(line.data() + pos, buf.data(), len); pos += len; } void write_single(const std::string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template void write_single(const std::vector& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; std::array, 100> Printer::small = [] { std::array, 100> table; for (int i = 0; i <= 99; i++) { table[i][1] = char('0' + (i % 10)); table[i][0] = char('0' + (i / 10 % 10)); } return table; }(); std::array Printer::tens = [] { std::array table; for (int i = 0; i < 20; i++) { table[i] = 1; for (int j = 0; j < i; j++) { table[i] *= 10; } } return table; }(); } // namespace yosupo using namespace yosupo; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template using V = vector; template using VV = V>; #ifdef LOCAL ostream& operator<<(ostream& os, __int128_t x) { if (x < 0) { os << "-"; x *= -1; } if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } ostream& operator<<(ostream& os, __uint128_t x) { if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } template ostream& operator<<(ostream& os, const pair& p); template ostream& operator<<(ostream& os, const V& v); template ostream& operator<<(ostream& os, const deque& v); template ostream& operator<<(ostream& os, const array& a); template ostream& operator<<(ostream& os, const set& s); template ostream& operator<<(ostream& os, const map& m); template ostream& operator<<(ostream& os, const pair& p) { return os << "P(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const V& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const deque& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const array& a) { os << "["; bool f = false; for (auto d : a) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const set& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const multiset& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const map& s) { os << "{"; bool f = false; for (auto p : s) { if (f) os << ", "; f = true; os << p.first << ": " << p.second; } return os << "}"; } struct PrettyOS { ostream& os; bool first; template auto operator<<(T&& x) { if (!first) os << ", "; first = false; os << x; return *this; } }; template void dbg0(T&&... t) { (PrettyOS{cerr, true} << ... << t); } #define dbg(...) \ do { \ cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \ dbg0(__VA_ARGS__); \ cerr << endl; \ } while (false); #else #define dbg(...) #endif Scanner sc = Scanner(stdin); Printer pr = Printer(stdout); int main() { int n, p1, p2; sc.read(n, p1, p2); VV v1(p1); VV v2(p2); for (int i = 0; i < p1; i++) { int l; sc.read(l); v1[i] = V(l + 1); for (int j = 0; j <= l; j++) { sc.read(v1[i][j]); } } for (int i = 0; i < p2; i++) { int l; sc.read(l); v2[i] = V(l + 1); for (int j = 0; j <= l; j++) { sc.read(v2[i][j]); } } int v = 0; V st1(p1), st2(p2); for (int i = 0; i < p1; i++) { st1[i] = v; v += int(v1[i].size()) - 1; } for (int i = 0; i < p2; i++) { st2[i] = v; v += int(v2[i].size()) - 1; } int sv = v, tv = v + 1; v += 2; V vis1(n + 2, -1), vis2(n + 2, -1); int ans = 0; atcoder::mf_graph g(v); for (int i = 0; i < p1; i++) { int l = int(v1[i].size()) - 1; for (int j = 0; j + 1 < l; j++) { // s s s ... s, t t t g.add_edge(st1[i] + j + 1, st1[i] + j, TEN(9)); } g.add_edge(sv, st1[i], TEN(9)); for (int j = 0; j < l; j++) { ans++; g.add_edge(sv, st1[i] + j, 1); } for (int j = 1; j < l; j++) { vis1[v1[i][j]] = st1[i] + j - 1; } } for (int i = 0; i < p2; i++) { int l = int(v2[i].size()) - 1; for (int j = 0; j + 1 < l; j++) { g.add_edge(st2[i] + j + 1, st2[i] + j, TEN(9)); } g.add_edge(st2[i] + l - 1, tv, TEN(9)); for (int j = 1; j < l; j++) { vis2[v2[i][j]] = st2[i] + j - 1; } } for (int i = 1; i <= n; i++) { if (vis1[i] != -1 && vis2[i] != -1) { g.add_edge(vis1[i], vis2[i], TEN(9)); g.add_edge(vis2[i], vis1[i], TEN(9)); g.add_edge(vis1[i] + 1, vis2[i] + 1, TEN(9)); g.add_edge(vis2[i] + 1, vis1[i] + 1, TEN(9)); } } ans -= g.flow(sv, tv, ans + 1); pr.writeln(ans); return 0; }