巴已己很愛來你家串珠珠，他非常喜歡將一堆珠珠穿成一個項鍊，而根據珠珠的形狀共可以分成 $n$ 種，但現在這些珠珠很麻煩，珠珠有很多都有獨特的形狀，
導致每種珠珠只能跟部份其他種類的珠珠串起來的，也就是每種珠珠的下一顆珠珠只能是固定的某些種類（有可能包含自己的種類），經過你嚴謹的研究後共發現了 $m$ 組能接起來的珠珠組合。
而你家非常有錢，每種珠珠都有無限多顆，所以巴已己可以串出非常長的珠珠項鍊。

當巴已己串完他的珠珠項鍊後，會請你幫這條項鍊上的每顆珠珠都塗上顏色。為此你需要事先準備 $k$ 種顏料，不論巴已己串出來的項鍊長怎樣，
你都存在一種幫項鍊塗色的方法，使得每種顏料都曾被使用到，且項鍊上每種顏色的珠珠數量都一樣。因巴已己覺得項鍊越多顏色越漂亮，
為了滿足他的期望你需要找出最大的 $k$ 為何。