Masquerade Mask Classes

At the annual masquerade ball, each participant wears a specially‐designed mask with a unique number. The masks are divided into \(k\) classes (with \(k\geq 3\)). A special technology ensures that a person wearing a mask of class \(i\) can only see the mask number of someone wearing a mask of class \(i+1\) (and a person with a mask from class \(k\) can only see the number on a mask of class \(1\)).

Dongdong collected several pieces of information. Each record is given in the form of two integers \(a\) and \(b\), meaning that the person whose mask number is \(a\) saw the mask number \(b\). If we assign an unknown class \(f(x)\) to each mask number \(x\) (with values in \(\{1,2,\dots,k\}\)), then every observation gives the constraint

[ f(b) \equiv f(a) + 1 \pmod{k}. ]

Using all the observations (which might be incomplete), compute the minimum and maximum possible number of mask classes \(k\) that could be consistent with the data. Note that if the observations do not impose any upper bound, then the maximum count is "Infinite". (Also note that \(k\ge 3\) by the problem statement.)

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of observations. Each of the following \(n\) lines contains two integers \(a\) and \(b\) (\(1 \le a,b \le 10^9\)), representing that the person with mask number \(a\) saw the mask number of someone — which implies the constraint \(f(b) \equiv f(a) + 1 \pmod{k}\).

outputFormat

Output two space‐separated values: the minimum and the maximum possible number of mask classes \(k\) that are consistent with the observations. If there is no upper bound, output the word "Infinite" in place of the maximum.

sample

3
1 2
2 3
3 1

3 3