This problem is an exercise of Chinese reminder theorem.

What is Chinese reminder theorem?

It claims that, given \(N\) pairs of integers \((r_i, m_i)\), there is a unique integer \(x\) between \(0\) (inclusive) and \(\mathrm{LCM}(m_1,m_2,\ldots,m_N)\) (exclusive) such that

• \(x \bmod m_i = r_i\ (1\leq i \leq N)\),

if \(m_i\) are coprime.

For example, AtCoder Library enables us to find such \(x\) in an \(\mathrm{O}(N\log(\mathrm{LCM}(m_1,m_2,\ldots,m_N)))\) time if it is uniquely determined.

Solution to this problem

For some \(A\), note that if a graph with edges \(i\to A_i\) has a cycle of length \(c\), then we can determine \(N\bmod {c}\) from \(B\).

The first idea would be using \(2,3,5,\ldots,23,29\) (all primes not exceeding \(29\)), from which we can reconstruct \(N\) by Chinese remainder theorem because \(\mathrm{LCM}(2,3,5,\ldots,23,29) = 6469693230 \geq 10^9\), but unfortunately, \(2+3+5+\ldots+23+29=129 > 110\) so it exceeds the constraints of \(M\).

Instead, we can adopt \(4,9,5\ldots,19,23\) as the lengths of the cycles, because \(N\) and \(M\) both satisfy the conditions since \(\mathrm{LCM}(4,9,5,\ldots,19,23) =1338557220 \geq 10^9\) \(4+9+5+\ldots+19+23=108 \leq 110\); thus we can get accepted.