1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define p pair<i128, i128>
#define i128 __int128_t

vector<i128> *in;
vector<i128> *out;
pair<i128, i128> *dp;

void preprocess(i128 n) {
  ll x, cnt;
  for (i128 i = 1; i <= n; i++) {
    cin >> cnt;
    for (i128 j = 0; j < cnt; j++) {
      cin >> x;
      out[i].push_back(x);
      in[x].push_back(i);
    }
  }
}

p sum(const p &one, const p &sec) {
  p res;
  res.s = (one.s * sec.s) / __gcd(one.s, sec.s);
  i128 sum = (one.f * res.s / one.s) + (sec.f * res.s / sec.s);

  res.f = sum / __gcd(sum, res.s);
  res.s = res.s / __gcd(sum, res.s);

  return res;
}

p multiply(p one, p sec) {
  p res;

  i128 gcd_ab = __gcd(one.f, one.s);
  one.f /= gcd_ab;
  one.s /= gcd_ab;

  i128 gcd_cd = __gcd(sec.f, sec.s);
  sec.f /= gcd_cd;
  sec.s /= gcd_cd;

  i128 gcd_ad = __gcd(one.f, sec.s);
  one.f /= gcd_ad;
  sec.s /= gcd_ad;

  i128 gcd_cb = __gcd(one.s, sec.f);
  one.s /= gcd_cb;
  sec.f /= gcd_cb;

  res.f = one.f * sec.f;
  res.s = one.s * sec.s;

  i128 gcd = __gcd(res.f, res.s);
  res.f /= gcd;
  res.s /= gcd;

  return res;
}

i128 nww(i128 a, i128 b) {
  return a / __gcd(a, b) * b;
}

ll solve(i128 n) {
  preprocess(n);
  dp[1] = {1, 1};
  for (i128 i = 2; i <= n; i++) {
    dp[i] = {0, 1};
    for (auto x : in[i]) {
      p sec = multiply(dp[x], {(i128)1, (i128)out[x].size()});
      dp[i] = sum(dp[i], sec);
    }
  }

  i128 gcd = dp[1].s;
  for (i128 i = 2; i <= n; i++) {
    gcd = nww(gcd, dp[i].s);
  }

  return gcd;
}

int main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);

  ll n;
  cin >> n;

  in = new vector<i128>[n + 1];
  out = new vector<i128>[n + 1];
  dp = new pair<i128, i128>[n + 1];

  ll res = solve(n);
  cout << res << '\n';

  return 0;
}