QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198433#3612. All in the FamilyisaunoyaAC ✓1ms3944kbC++233.7kb2023-10-03 13:50:532023-10-03 13:50:53

Judging History

This is the latest submission verdict.

  • [2023-10-03 13:50:53]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3944kb
  • [2023-10-03 13:50:53]
  • Submitted

answer

#include <bits/stdc++.h>
#include <string>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
  x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
  x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

map<string, int> mp;
int c = 0;
vi g[100];
int f[100];
void solve() {
  int n, m;
  cin >> n >> m;
  memset(f, -1, sizeof f);
  for (int i = 0; i < n; i++) {
    string p;
    cin >> p;
    if (!mp.count(p)) {
      mp[p] = c++;
    }
    int w = mp[p];
    int k;
    cin >> k;
    while (k--) {
      string v;
      cin >> v;
      if (!mp.count(v)) {
        mp[v] = c++;
      }
      int q = mp[v];
      g[w].pb(q);
      f[q] = w;
    }
  }
  int rt = -1;
  rep(i, c) if (f[i] == -1) rt = i;
  vi d(c, -1);
  queue<int> q;
  d[rt] = 0;
  q.emplace(rt);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (d[v] == -1) {
        q.emplace(v);
        d[v] = d[u] + 1;
      }
    }
  }
  while (m--) {
    string a, b;
    cin >> a >> b;
    int A = mp[a];
    int B = mp[b];
    int aa = A, bb = B;
    while (d[aa] > d[bb])
      aa = f[aa];
    while (d[aa] < d[bb])
      bb = f[bb];
    while (aa != bb)
      aa = f[aa], bb = f[bb];
    int C = aa;
    if (A == C || B == C) {
      if (d[A] < d[B]) {
        swap(a, b);
        swap(A, B);
      }
      int w = d[A] - d[C];
      if (w == 1) {
        cout << a << " is the child of " << b << "\n";
      } else {
        w -= 2;
        cout << a << " is the ";
        while (w--)
          cout << "great ";
        cout << "grandchild of " << b << "\n";
      }
    } else {
      int w1 = d[A] - d[C];
      int w2 = d[B] - d[C];
      if (w1 == 1 && w2 == 1) {
        cout << a << " and " << b << " are siblings\n";
      } else {
        // debug(a,b,w1,w2);
        auto id = [&](int x) {
          if (x == 11 || x == 12 || x == 13) {
            cout << x << "th ";
            return;
          }
          if (x % 10 == 1) {
            cout << x << "st ";
            return;
          }
          if (x % 10 == 2) {
            cout << x << "nd ";
            return;
          }
          if (x % 10 == 3) {
            cout << x << "rd ";
            return;
          }
          cout << x << "th ";
        };
        string time = "time";
        if (abs(w1 - w2) >= 2)
          time += "s";
        cout << a << " and " << b << " are ", id(min(w1, w2) - 1),
            cout << "cousins";
        if (w1 - w2)
          cout << ", " << abs(w1 - w2) << " " << time << " removed\n";
        else
          cout << "\n";
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3892kb

input:

4 5
Horatio 1 Irene
Chris 2 Gina Horatio
Alice 3 Dan Emily Frank
Bob 2 Alice Chris
Irene Bob
Dan Frank
Chris Emily
Alice Chris
Dan Irene

output:

Irene is the great grandchild of Bob
Dan and Frank are siblings
Chris and Emily are 0th cousins, 1 time removed
Alice and Chris are siblings
Dan and Irene are 1st cousins, 1 time removed

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

4 6
A 4 B C D E
H 3 I J K
C 2 F G
D 1 H
G C
H A
F G
F H
F K
B K

output:

G is the child of C
H is the grandchild of A
F and G are siblings
F and H are 1st cousins
F and K are 1st cousins, 1 time removed
B and K are 0th cousins, 2 times removed

result:

ok 6 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

13 12
A 2 P C
P 1 B
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
K 1 L
L 1 M
M 1 N
B C
B D
B E
B F
B G
B H
B I
B J
B K
B L
B M
B N

output:

B and C are 0th cousins, 1 time removed
B and D are 1st cousins
B and E are 1st cousins, 1 time removed
B and F are 1st cousins, 2 times removed
B and G are 1st cousins, 3 times removed
B and H are 1st cousins, 4 times removed
B and I are 1st cousins, 5 times removed
B and J are 1st cousins, 6 times...

result:

ok 12 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

14 12
A 2 P C
P 1 Q
Q 1 B
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
K 1 L
L 1 M
M 1 N
B C
B D
B E
B F
B G
B H
B I
B J
B K
B L
B M
B N

output:

B and C are 0th cousins, 2 times removed
B and D are 1st cousins, 1 time removed
B and E are 2nd cousins
B and F are 2nd cousins, 1 time removed
B and G are 2nd cousins, 2 times removed
B and H are 2nd cousins, 3 times removed
B and I are 2nd cousins, 4 times removed
B and J are 2nd cousins, 5 times...

result:

ok 12 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

19 100
A 2 L B
L 1 M
M 1 N
N 1 O
O 1 P
P 1 Q
Q 1 R
R 1 S
S 1 T
T 1 U
B 1 C
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
B L
B M
B N
B O
B P
B Q
B R
B S
B T
B U
C L
C M
C N
C O
C P
C Q
C R
C S
C T
C U
D L
D M
D N
D O
D P
D Q
D R
D S
D T
D U
E L
E M
E N
E O
E P
E Q
E R
E S
E T
E U
F L
F M
F N
F O
F...

output:

B and L are siblings
B and M are 0th cousins, 1 time removed
B and N are 0th cousins, 2 times removed
B and O are 0th cousins, 3 times removed
B and P are 0th cousins, 4 times removed
B and Q are 0th cousins, 5 times removed
B and R are 0th cousins, 6 times removed
B and S are 0th cousins, 7 times r...

result:

ok 100 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

17 100
A 2 B C
B 2 D E
C 1 F
D 1 G
E 1 H
F 1 I
G 2 J K
H 2 L M
I 1 N
J 1 O
K 1 P
L 2 Q R
M 2 S T
N 2 U V
O 2 W X
P 1 Y
Q 1 Z
N R
R Z
L U
Z A
Z L
B V
V D
M D
K G
G M
Z R
K Q
X O
R I
K W
A F
D U
J K
A E
Z N
K N
P S
O Q
Y Z
G U
K O
Z L
O Y
S Y
L Y
I A
N W
F D
C Z
L G
E X
N E
N K
O J
X Y
R L
A Q
U S
G U...

output:

N and R are 3rd cousins, 1 time removed
R and Z are 0th cousins, 1 time removed
L and U are 3rd cousins, 1 time removed
Z is the great great great great grandchild of A
Z is the grandchild of L
B and V are 0th cousins, 4 times removed
V and D are 1st cousins, 3 times removed
M and D are 0th cousins,...

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

14 100
A 1 B
B 3 C D E
C 1 F
D 3 G H I
E 3 J K L
F 1 M
G 2 N O
H 2 P Q
I 2 R S
J 3 T U V
K 1 W
L 1 X
M 1 Y
N 1 Z
N Y
N T
W C
J L
U N
S A
W Q
E H
N T
H Y
B X
S H
T J
N K
Q P
I X
Y B
F M
U J
U H
J V
U M
Y Z
V L
E L
L Z
V Q
P U
Z D
B O
H F
Y K
L A
Q P
F C
I F
A E
R V
V G
R S
C R
T V
R U
J K
K O
O P
W P...

output:

N and Y are 2nd cousins, 1 time removed
N and T are 2nd cousins
W and C are 0th cousins, 2 times removed
J and L are siblings
U and N are 2nd cousins
S is the great great grandchild of A
W and Q are 2nd cousins
E and H are 0th cousins, 1 time removed
N and T are 2nd cousins
H and Y are 1st cousins, ...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

10 100
A 1 B
B 3 C D E
C 2 F G
D 4 H I J K
E 1 L
F 2 M N
G 4 O P Q R
H 2 S T
I 5 U V W X Y
J 1 Z
I O
H A
D R
P Q
B C
V P
O M
Z E
A T
G U
Z V
N O
M R
R F
H R
Z O
V F
Z P
O Z
Y W
E G
W U
V E
P O
Q V
T I
K O
M X
T L
P D
E F
L O
J S
F G
V A
U F
Z H
P J
A U
P S
Y H
R U
O K
A T
K X
Z U
B U
R S
Y J
P C
N V...

output:

I and O are 1st cousins, 1 time removed
H is the great grandchild of A
D and R are 0th cousins, 2 times removed
P and Q are siblings
C is the child of B
V and P are 2nd cousins
O and M are 1st cousins
Z and E are 0th cousins, 2 times removed
T is the great great grandchild of A
G and U are 1st cousi...

result:

ok 100 lines

Test #9:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

31 500
A 2 B C
B 1 D
C 2 E F
D 1 G
E 1 H
F 1 I
G 2 J K
H 2 L M
I 1 N
J 1 O
K 2 P Q
L 2 R S
M 2 T U
N 2 V W
O 1 X
P 1 Y
Q 2 Z AA
R 1 AB
S 2 AC AD
T 2 AE AF
U 2 AG AH
V 1 AI
W 2 AJ AK
X 2 AL AM
Y 2 AN AO
Z 2 AP AQ
AA 2 AR AS
AB 1 AT
AC 1 AU
AD 2 AV AW
AE 1 AX
AM E
AE U
Y AE
Z F
J AD
S AX
B AH
C A
C B
...

output:

AM and E are 1st cousins, 5 times removed
AE and U are 0th cousins, 1 time removed
Y and AE are 5th cousins
Z and F are 1st cousins, 4 times removed
J and AD are 3rd cousins, 2 times removed
S and AX are 1st cousins, 2 times removed
B and AH are 0th cousins, 5 times removed
C is the child of A
C and...

result:

ok 500 lines

Test #10:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

28 500
A 3 B C D
B 3 E F G
C 2 H I
D 2 J K
E 1 L
F 1 M
G 1 N
H 3 O P Q
I 1 R
J 1 S
K 1 T
L 2 U V
M 1 W
N 1 X
O 2 Y Z
P 3 AA AB AC
Q 1 AD
R 3 AE AF AG
S 2 AH AI
T 3 AJ AK AL
U 1 AM
V 1 AN
W 1 AO
X 2 AP AQ
Y 3 AR AS AT
Z 1 AU
AA 1 AV
AB 2 AW AX
M AK
T D
Y AH
AM B
V W
AD K
AN R
I Z
N AR
AL U
AL AM
AL H...

output:

M and AK are 2nd cousins, 1 time removed
T is the grandchild of D
Y and AH are 3rd cousins
AM is the great great grandchild of B
V and W are 2nd cousins
AD and K are 1st cousins, 2 times removed
AN and R are 2nd cousins, 2 times removed
I and Z are 0th cousins, 2 times removed
N and AR are 2nd cousi...

result:

ok 500 lines

Test #11:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

16 500
A 3 B C D
B 3 E F G
C 1 H
D 3 I J K
E 1 L
F 5 M N O P Q
G 3 R S T
H 3 U V W
I 5 X Y Z AA AB
J 3 AC AD AE
K 1 AF
L 2 AG AH
M 4 AI AJ AK AL
N 3 AM AN AO
O 4 AP AQ AR AS
P 5 AT AU AV AW AX
K Y
AL AD
D H
AP AI
AX AP
V D
AN G
AH D
AL AF
AJ AB
AU M
H AP
O C
K R
B I
AB V
AT Y
AI AU
G AH
B V
AE AG
AU...

output:

K and Y are 0th cousins, 1 time removed
AL and AD are 2nd cousins, 1 time removed
D and H are 0th cousins, 1 time removed
AP and AI are 1st cousins
AX and AP are 1st cousins
V and D are 0th cousins, 2 times removed
AN and G are 0th cousins, 2 times removed
AH and D are 0th cousins, 3 times removed
A...

result:

ok 500 lines

Test #12:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

11 500
A 2 B C
B 1 D
C 3 E F G
D 6 H I J K L M
E 7 N O P Q R S T
F 6 U V W X Y Z
G 6 AA AB AC AD AE AF
H 8 AG AH AI AJ AK AL AM AN
I 6 AO AP AQ AR AS AT
J 2 AU AV
K 2 AW AX
U A
T AS
O P
L G
AE A
U AU
Q AW
I AK
T AG
Y J
I AT
P Y
T AR
AB P
AA AI
C AU
Z M
V Z
AS I
AI AJ
I R
AW S
U R
AG L
K N
R T
AR D
A...

output:

U is the great grandchild of A
T and AS are 2nd cousins, 1 time removed
O and P are siblings
L and G are 1st cousins, 1 time removed
AE is the great grandchild of A
U and AU are 2nd cousins, 1 time removed
Q and AW are 2nd cousins, 1 time removed
I and AK are 0th cousins, 1 time removed
T and AG are...

result:

ok 500 lines

Test #13:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

10 21
A 1 B
B 1 C
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
A B
A C
A D
A E
A F
A G
A H
A I
A K
B A
C A
D A
E A
F A
G A
H A
I A
J A
K A
B I
H C

output:

B is the child of A
C is the grandchild of A
D is the great grandchild of A
E is the great great grandchild of A
F is the great great great grandchild of A
G is the great great great great grandchild of A
H is the great great great great great grandchild of A
I is the great great great great great g...

result:

ok 21 lines

Test #14:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

67 500
A 1 B
B 1 C
C 1 D
D 1 E
E 2 F G
F 2 H I
G 1 J
H 1 K
I 1 L
J 1 M
K 2 N O
L 1 P
M 2 Q R
N 2 S T
O 2 U V
P 1 W
Q 2 X Y
R 1 Z
S 2 AA AB
T 1 AC
U 2 AD AE
V 2 AF AG
W 2 AH AI
X 1 AJ
Y 1 AK
Z 1 AL
AA 1 AM
AB 2 AN AO
AC 2 AP AQ
AD 1 AR
AE 2 AS AT
AF 2 AU AV
AG 2 AW AX
AH 1 AY
AI 2 BZ BA
AJ 1 BB
AK 2 ...

output:

G and CI are 0th cousins, 8 times removed
T is the great great great great grandchild of D
G and U are 0th cousins, 4 times removed
Y and BO are 4th cousins, 3 times removed
BO and T are 1st cousins, 3 times removed
CH and CI are 7th cousins, 1 time removed
CR and BW are 3rd cousins, 1 time removed
...

result:

ok 500 lines

Test #15:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

52 500
A 2 B C
B 3 D E F
C 1 G
D 2 H I
E 2 J K
F 3 L M N
G 1 O
H 3 P Q R
I 3 S T U
J 1 V
K 1 W
L 2 X Y
M 2 Z AA
N 1 AB
O 2 AC AD
P 2 AE AF
Q 3 AG AH AI
R 2 AJ AK
S 2 AL AM
T 3 AN AO AP
U 1 AQ
V 3 AR AS AT
W 2 AU AV
X 3 AW AX AY
Y 3 BZ BA BB
Z 1 BC
AA 2 BD BE
AB 2 BF BG
AC 1 BH
AD 3 BI BJ BK
AE 2 BL ...

output:

CS and CK are 4th cousins
BG and L are 0th cousins, 2 times removed
BH and AO are 4th cousins
M and H are 1st cousins
BA is the great great grandchild of B
Q and R are siblings
BT and J are 1st cousins, 3 times removed
CZ and BR are 3rd cousins
BD and U are 2nd cousins, 1 time removed
O and CN are 2...

result:

ok 500 lines

Test #16:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

34 500
A 3 B C D
B 1 E
C 2 F G
D 3 H I J
E 4 K L M N
F 5 O P Q R S
G 2 T U
H 4 V W X Y
I 5 Z AA AB AC AD
J 1 AE
K 2 AF AG
L 1 AH
M 1 AI
N 3 AJ AK AL
O 4 AM AN AO AP
P 3 AQ AR AS
Q 5 AT AU AV AW AX
R 1 AY
S 2 BZ BA
T 5 BB BC BD BE BF
U 5 BG BH BI BJ BK
V 3 BL BM BN
W 1 BO
X 5 BP BQ BR BS BT
Y 3 BU BV...

output:

CV and BG are 3rd cousins, 1 time removed
AH and CA are 3rd cousins
V and CA are 1st cousins, 1 time removed
BZ and BY are 3rd cousins
BN and BP are 1st cousins
V and CF are 1st cousins, 1 time removed
C and CD are 0th cousins, 3 times removed
CA and U are 2nd cousins, 1 time removed
CD and CH are 1...

result:

ok 500 lines

Test #17:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

15 500
A 1 B
B 8 C D E F G H I J
C 8 K L M N O P Q R
D 7 S T U V W X Y
E 5 Z AA AB AC AD
F 8 AE AF AG AH AI AJ AK AL
G 10 AM AN AO AP AQ AR AS AT AU AV
H 9 AW AX AY BZ BA BB BC BD BE
I 10 BF BG BH BI BJ BK BL BM BN BO
J 6 BP BQ BR BS BT BU
K 8 BV BW BX BY CZ CA CB CC
L 6 CD CE CF CG CH CI
M 9 CJ CK ...

output:

H and AS are 0th cousins, 1 time removed
AW and J are 0th cousins, 1 time removed
X and CR are 1st cousins, 1 time removed
BG and CP are 1st cousins, 1 time removed
AQ and AA are 1st cousins
BJ is the grandchild of B
BC and AB are 1st cousins
AX and BU are 1st cousins
AC and BC are 1st cousins
CK an...

result:

ok 500 lines

Test #18:

score: 0
Accepted
time: 1ms
memory: 3940kb

input:

10 500
A 16 B C D E F G H I J K L M N O P Q
B 16 R S T U V W X Y Z AA AB AC AD AE AF AG
C 12 AH AI AJ AK AL AM AN AO AP AQ AR AS
D 5 AT AU AV AW AX
E 3 AY BZ BA
F 4 BB BC BD BE
G 2 BF BG
H 17 BH BI BJ BK BL BM BN BO BP BQ BR BS BT BU BV BW BX
I 12 BY CZ CA CB CC CD CE CF CG CH CI CJ
J 12 CK CL CM CN...

output:

L and CB are 0th cousins, 1 time removed
BL and BW are siblings
AK and H are 0th cousins, 1 time removed
BS and CO are 1st cousins
AF and AI are 1st cousins
V is the grandchild of A
CU and N are 0th cousins, 1 time removed
BP and V are 1st cousins
CG and BG are 1st cousins
BB and CA are 1st cousins
...

result:

ok 500 lines

Test #19:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

5 500
A 26 B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA
B 50 AB AC AD AE AF AG AH AI AJ AK AL AM AN AO AP AQ AR AS AT AU AV AW AX AY BZ BA BB BC BD BE BF BG BH BI BJ BK BL BM BN BO BP BQ BR BS BT BU BV BW BX BY
C 8 CZ CA CB CC CD CE CF CG
D 12 CH CI CJ CK CL CM CN CO CP CQ CR CS
E 3 CT CU CV...

output:

AK and I are 0th cousins, 1 time removed
CR and W are 0th cousins, 1 time removed
J is the child of A
BW and AR are siblings
BV is the grandchild of A
BM and AE are siblings
BW and D are 0th cousins, 1 time removed
AT and U are 0th cousins, 1 time removed
CS and AO are 1st cousins
AN and R are 0th c...

result:

ok 500 lines

Test #20:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

66 1000
A 1 B
B 2 C D
C 2 E F
D 2 G H
E 2 I J
F 1 K
G 2 L M
H 2 N O
I 1 P
J 1 Q
K 2 R S
L 1 T
M 2 U V
N 1 W
O 2 X Y
P 2 Z AA
Q 1 AB
R 1 AC
S 2 AD AE
T 2 AF AG
U 1 AH
V 1 AI
W 1 AJ
X 1 AK
Y 2 AL AM
Z 2 AN AO
AA 2 AP AQ
AB 2 AR AS
AC 2 AT AU
AD 1 AV
AE 1 AW
AF 1 AX
AG 2 AY BZ
AH 1 BA
AI 2 BB BC
AJ 1 B...

output:

AS and BV are 4th cousins, 1 time removed
AP and F are 0th cousins, 4 times removed
CJ and CQ are 6th cousins, 1 time removed
S and AM are 3rd cousins, 1 time removed
BE is the child of AK
CP is the great grandchild of Z
BY and CZ are 2nd cousins
BO and BU are 5th cousins
AW and G are 1st cousins, 4...

result:

ok 1000 lines

Test #21:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

32 1000
A 4 B C D E
B 5 F G H I J
C 3 K L M
D 5 N O P Q R
E 3 S T U
F 5 V W X Y Z
G 5 AA AB AC AD AE
H 2 AF AG
I 1 AH
J 1 AI
K 5 AJ AK AL AM AN
L 2 AO AP
M 3 AQ AR AS
N 2 AT AU
O 3 AV AW AX
P 1 AY
Q 3 BZ BA BB
R 3 BC BD BE
S 4 BF BG BH BI
T 3 BJ BK BL
U 4 BM BN BO BP
V 1 BQ
W 3 BR BS BT
X 4 BU BV BW...

output:

AK and F are 1st cousins, 1 time removed
AT and BE are 1st cousins
S and BY are 1st cousins, 2 times removed
J and K are 1st cousins
CI and CJ are 1st cousins
L and CF are 1st cousins, 2 times removed
AG and CE are 1st cousins, 1 time removed
BB is the grandchild of D
I and BI are 1st cousins, 1 tim...

result:

ok 1000 lines

Test #22:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

20 1000
A 3 B C D
B 9 E F G H I J K L M
C 8 N O P Q R S T U
D 9 V W X Y Z AA AB AC AD
E 2 AE AF
F 2 AG AH
G 3 AI AJ AK
H 10 AL AM AN AO AP AQ AR AS AT AU
I 1 AV
J 2 AW AX
K 4 AY BZ BA BB
L 8 BC BD BE BF BG BH BI BJ
M 7 BK BL BM BN BO BP BQ
N 3 BR BS BT
O 5 BU BV BW BX BY
P 9 CZ CA CB CC CD CE CF CG ...

output:

AB and AX are 1st cousins, 1 time removed
I and CC are 1st cousins, 1 time removed
O and Z are 1st cousins
BU and N are 0th cousins, 1 time removed
CO and AG are 2nd cousins
X and CN are 1st cousins, 1 time removed
AY and AF are 1st cousins
M and BT are 1st cousins, 1 time removed
BW and CZ are 1st ...

result:

ok 1000 lines

Test #23:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

11 1000
A 1 B
B 7 C D E F G H I
C 14 J K L M N O P Q R S T U V W
D 14 X Y Z AA AB AC AD AE AF AG AH AI AJ AK
E 12 AL AM AN AO AP AQ AR AS AT AU AV AW
F 8 AX AY BZ BA BB BC BD BE
G 18 BF BG BH BI BJ BK BL BM BN BO BP BQ BR BS BT BU BV BW
H 3 BX BY CZ
I 13 CA CB CC CD CE CF CG CH CI CJ CK CL CM
J 5 CN...

output:

BA and Y are 1st cousins
AI and CR are 1st cousins, 1 time removed
CS and Q are 0th cousins, 1 time removed
CB and K are 1st cousins
AF and AT are 1st cousins
Q and BL are 1st cousins
AJ is the child of D
CA and CO are 1st cousins, 1 time removed
L and CF are 1st cousins
I and M are 0th cousins, 1 t...

result:

ok 1000 lines

Test #24:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

1 10
A 12 B C D E F G H I J K L M
A B
B A
B M
M B
L C
M D
A M
G J
J G
E F

output:

B is the child of A
B is the child of A
B and M are siblings
M and B are siblings
L and C are siblings
M and D are siblings
M is the child of A
G and J are siblings
J and G are siblings
E and F are siblings

result:

ok 10 lines

Test #25:

score: 0
Accepted
time: 1ms
memory: 3944kb

input:

4 1000
A 29 B C D E F G H I J K L M N O P Q R S T U V W X Y Z AA AB AC AD
B 15 AE AF AG AH AI AJ AK AL AM AN AO AP AQ AR AS
C 8 AT AU AV AW AX AY BZ BA
D 47 BB BC BD BE BF BG BH BI BJ BK BL BM BN BO BP BQ BR BS BT BU BV BW BX BY CZ CA CB CC CD CE CF CG CH CI CJ CK CL CM CN CO CP CQ CR CS CT CU CV
B ...

output:

AJ is the child of B
BN and CU are siblings
CO and Q are 0th cousins, 1 time removed
CU and CT are siblings
AG and AV are 1st cousins
AA and CN are 0th cousins, 1 time removed
CV and AI are 1st cousins
AH and BC are 1st cousins
P and AI are 0th cousins, 1 time removed
T and AA are siblings
BE and AE...

result:

ok 1000 lines

Test #26:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

97 49
A 2 C RC
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
K 1 L
L 1 M
M 1 N
N 1 O
O 1 P
P 1 Q
Q 1 R
R 1 S
S 1 T
T 1 U
U 1 V
V 1 W
W 1 X
X 1 Y
Y 1 Z
Z 1 AA
AA 1 AB
AB 1 AC
AC 1 AD
AD 1 AE
AE 1 AF
AF 1 AG
AG 1 AH
AH 1 AI
AI 1 AJ
AJ 1 AK
AK 1 AL
AL 1 AM
AM 1 AN
AN 1 AO
AO 1 AP
AP 1 AQ
AQ 1 AR
AR 1...

output:

C and RC are siblings
D and RD are 1st cousins
E and RE are 2nd cousins
F and RF are 3rd cousins
G and RG are 4th cousins
H and RH are 5th cousins
I and RI are 6th cousins
J and RJ are 7th cousins
K and RK are 8th cousins
L and RL are 9th cousins
M and RM are 10th cousins
N and RN are 11th cousins
O...

result:

ok 49 lines

Test #27:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

98 98
A 2 B C
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
K 1 L
L 1 M
M 1 N
N 1 O
O 1 P
P 1 Q
Q 1 R
R 1 S
S 1 T
T 1 U
U 1 V
V 1 W
W 1 X
X 1 Y
Y 1 Z
Z 1 AA
AA 1 AB
AB 1 AC
AC 1 AD
AD 1 AE
AE 1 AF
AF 1 AG
AG 1 AH
AH 1 AI
AI 1 AJ
AJ 1 AK
AK 1 AL
AL 1 AM
AM 1 AN
AN 1 AO
AO 1 AP
AP 1 AQ
AQ 1 AR
AR 1 ...

output:

B and C are siblings
B and D are 0th cousins, 1 time removed
B and E are 0th cousins, 2 times removed
B and F are 0th cousins, 3 times removed
B and G are 0th cousins, 4 times removed
B and H are 0th cousins, 5 times removed
B and I are 0th cousins, 6 times removed
B and J are 0th cousins, 7 times r...

result:

ok 98 lines

Test #28:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

9 25
A 2 B C
B 1 D
C 1 E
D 1 F
E 1 G
F 1 H
G 1 I
H 1 J
I 1 K
B C
D E
F G
H I
J K
B E
B G
B I
B K
C D
C F
C H
C J
D G
D I
D K
F I
F K
H K
E F
E H
E J
G H
G J
I J

output:

B and C are siblings
D and E are 1st cousins
F and G are 2nd cousins
H and I are 3rd cousins
J and K are 4th cousins
B and E are 0th cousins, 1 time removed
B and G are 0th cousins, 2 times removed
B and I are 0th cousins, 3 times removed
B and K are 0th cousins, 4 times removed
C and D are 0th cous...

result:

ok 25 lines

Test #29:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 5
A 1 B
B 1 C
C 2 D E
D 2 F I
E 2 G H
F H
I G
A F
G B
F E

output:

F and H are 1st cousins
I and G are 1st cousins
F is the great great grandchild of A
G is the great grandchild of B
F and E are 0th cousins, 1 time removed

result:

ok 5 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

5 5
Abby 1 Bob
Bob 1 Chris
Chris 2 Dan Edna
Dan 2 Fred Irene
Edna 2 Gene Harry
Fred Harry
Irene Gene
Abby Fred
Gene Bob
Fred Edna

output:

Fred and Harry are 1st cousins
Irene and Gene are 1st cousins
Fred is the great great grandchild of Abby
Gene is the great grandchild of Bob
Fred and Edna are 0th cousins, 1 time removed

result:

ok 5 lines

Test #31:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

5 5
ZAbby 1 ZBob
ZBob 1 ZChris
ZChris 2 ZDan ZEdna
ZDan 2 ZFred ZIrene
ZEdna 2 ZGene ZHarry
ZFred ZHarry
ZIrene ZGene
ZAbby ZFred
ZGene ZBob
ZFred ZEdna

output:

ZFred and ZHarry are 1st cousins
ZIrene and ZGene are 1st cousins
ZFred is the great great grandchild of ZAbby
ZGene is the great grandchild of ZBob
ZFred and ZEdna are 0th cousins, 1 time removed

result:

ok 5 lines

Test #32:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

13 780
A 3 B C D
B 3 E F G
C 3 H I J
D 3 K L M
E 3 N O P
F 3 Q R S
G 3 T U V
H 3 W X Y
I 3 Z AA AB
J 3 AC AD AE
K 3 AF AG AH
L 3 AI AJ AK
M 3 AL AM AN
A B
A C
A D
A E
A F
A G
A H
A I
A J
A K
A L
A M
A N
A O
A P
A Q
A R
A S
A T
A U
A V
A W
A X
A Y
A Z
A AA
A AB
A AC
A AD
A AE
A AF
A AG
A AH
A AI
A AJ...

output:

B is the child of A
C is the child of A
D is the child of A
E is the grandchild of A
F is the grandchild of A
G is the grandchild of A
H is the grandchild of A
I is the grandchild of A
J is the grandchild of A
K is the grandchild of A
L is the grandchild of A
M is the grandchild of A
N is the great ...

result:

ok 780 lines

Test #33:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

12 12
A 2 B C
C 1 D
D 1 E
E 1 F
F 1 G
G 1 H
H 1 I
I 1 J
J 1 K
K 1 L
L 1 M
M 1 N
B C
B D
B E
B F
B G
B H
B I
B J
B K
B L
B M
B N

output:

B and C are siblings
B and D are 0th cousins, 1 time removed
B and E are 0th cousins, 2 times removed
B and F are 0th cousins, 3 times removed
B and G are 0th cousins, 4 times removed
B and H are 0th cousins, 5 times removed
B and I are 0th cousins, 6 times removed
B and J are 0th cousins, 7 times r...

result:

ok 12 lines