Let us define integers \(X_{i, j}\) to be \(1\) if there is a string connecting Balls \(i\) and \(j\) in Takahashi’s toy, and to be \(0\) otherwise.
Similarly, let us define integers \(Y_{i, j}\) to be \(1\) if there is a string connecting Balls \(i\) and \(j\) in Aoki’s toy, and to be \(0\) otherwise.

Consider brute forcing all the permutations \(P\) of \((1, 2, \dots, N)\). Then \(P\) satisfies the conditions if and only if:

• for all \(1 \leq i \leq N, 1 \leq j \leq N\) it holds that \(X_{i, j} = Y_{P_i, P_j}\).

One can check if this condition is satisfied in \(O(N^2)\) time. Since there are \(N!\) possible \(P\)’s, the overall time complexity is \(O(N^2 \times N!)\), which will meet the time limit.

In order to iterate through all the permutations, we can use std::next_permutations in C++ or itertools.permutations in Python.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector x(n, vector<bool>(n)), y(n, vector<bool>(n));
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1, b -= 1;
        x[a][b] = x[b][a] = true;
    }
    for (int i = 0; i < m; ++i) {
        int c, d;
        cin >> c >> d;
        c -= 1, d -= 1;
        y[c][d] = y[d][c] = true;
    }
    vector<int> p(n);
    iota(begin(p), end(p), 0);
    int ans = 0;
    do {
        bool ok = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (x[i][j] != y[p[i]][p[j]]) {
                    ok = false;
                }
            }
        }
        if (ok) {
            cout << "Yes\n";
            return 0;
        }
    } while (next_permutation(begin(p), end(p)));
    cout << "No\n";
}

Sample code (Python) :

import itertools

n, m = map(int, input().split())
a = [[False] * n for _ in range(n)]
b = [[False] * n for _ in range(n)]

for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  a[u][v] = a[v][u] = True
  
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  b[u][v] = b[v][u] = True
  
ans = False
for p in itertools.permutations(range(n)):
  ok = True
  for i in range(n):
    for j in range(n):
      if a[i][j] != b[p[i]][p[j]]:
      	ok = False
  if ok:
    ans = True
print("Yes" if ans else "No")