Parallel Universes


Submit solution

Points: 15 (partial)
Time limit: 4.0s
Python 3 20.0s
Memory limit: 256M

Author:
Problem type

In this problem, dimensions of our "home" universe in can be represented the following way:

  • 1 \(\rightarrow\) 1
  • 2 \(\rightarrow\) 2
  • 3 \(\rightarrow\) 3

Meanwhile, using the same notation, dimensions of a parallel universe can be represented as:

  • 1 \(\rightarrow\) 2
  • 2 \(\rightarrow\) 3
  • 3 \(\rightarrow\) 1

Note the universes in this example both have sizes equal to three, since it has three dimensions.

To move from one universe to another, you have a machine that can teleport from some universe \(X\) to any other universe \(Y\) iff the two universes have at most two different representations of dimensions. For instance, you can not teleport from the first universe in the example above to the second one because there are three different dimensions in their representation. However, you can teleport from the second universe to the following one because only the second and third dimensions are changed while the first one remains the same:

  • 1 \(\rightarrow\) 2
  • 2 \(\rightarrow\) 1
  • 3 \(\rightarrow\) 3

You are given the representations of \(n\) universes that have the same size \(s\). Your job is to calculate for each universe the minimum number of teleportations needed to return to the "home" universe.

Input Specification

The first line of input contains two space separated integers \(n\) and \(s\) (\(1 \leq n, s, \leq 10^5\)) as described above. This is followed by \(n \times s\) lines -- the representations of the \(n\) universes. The first \(s\) lines describe the first universe, the second \(s\) lines describe the second universe, and so on... Every universe is described by \(s\) dimensions in the following format:

\(a\) -> \(b\)

Where (\(1 \leq a, b \leq s\)) and all \(a_i\) are pairwise distinct and all \(b_i\) are pairwise distinct.

See samples for a clear idea.

Output Specification

Output \(n\) integers each on a new line -- the \(i^{th}\) integer should represent the answer for the \(i^{th}\) universe in the same order as they appear in the input.

Scoring

  • \(s \leq 8\) and \(n \leq 20\) (\(2\) points).
  • \(s \leq 100\) and \(n \leq 100\) (\(3\) points).
  • \(n \times s \leq 10^7\) (\(4\) points).

Sample Input

2 5
1 -> 2
3 -> 4
4 -> 5
2 -> 3
5 -> 1
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5

Sample Output

4
0

Notes

\(-\) The order of the dimensions does not matter. For example, the following universes are identical:

  • 1 \(\rightarrow\) 1
  • 2 \(\rightarrow\) 2
  • 3 \(\rightarrow\) 3

And

  • 1 \(\rightarrow\) 1
  • 3 \(\rightarrow\) 3
  • 2 \(\rightarrow\) 2

\(-\) A "home" universe of size \(s\) is:

  • 1 \(\rightarrow\) 1
  • 2 \(\rightarrow\) 2
  • 3 \(\rightarrow\) 3
  • ...
  • s \(\rightarrow\) s

Comments

There are no comments at the moment.