В Шааззззляндии есть \(n\) городов, пронумерованных от \(0\) до \(n-1\). Гааззззляндией, бессмертным врагом Шааззззляндии, правит AaParsa.
Будучи главой разведывательной службы Гааззззляндии, AaParsa выполняет самую важную шпионскую миссию в истории Гааззззляндии на Шааззззляндии.
AaParsa установил \(m\) транспортных пушек в городах Шааззззляндии. \(i\)-я пушка установлена в городе \(a_i\) и изначально направлена на город \(b_i\).
Гарантируется, что в каждом из \(n\) городов есть по крайней мере одна транспортная пушка, и что никакие две пушки из одного города изначально не направлены на один и тот же город (то есть, все пары \((a_i, b_i)\) попарно различны).
AaParsa использовал очень продвинутую технологию для создания пушек, пушки вращаются каждую секунду. Другими словами, если \(i\)-я пушка направлена на город \(x\) в какую-то секунду, то в следующую секунду она будет нацелена на город \((x + 1) \mod n\).
Транспортные пушки, как следует из их названия, предназначены для транспортировки, в частности, для перевозки людей. Если вы используете \(i\)-ю пушку, чтобы запустить себя в направлении города, на который она сейчас нацелена, вы будете находиться в воздухе в течение \(c_i\) секунд, прежде чем достигнете цели.
Если вы все еще не поняли, использование \(i\)-й пушки на \(s\)-й секунде (что возможно, только если вы в данный момент находитесь в городе \(a_i\)) запустит вас в город \((b_i + s) \mod n\), и вы приземлитесь в нем через \(c_i\) секунд (таким образом, вы окажетесь там в \((s + c_i)\)-ю секунду). Обратите внимание, что пушка, из которой вы изначально стартовали, будет вращаться каждую секунду, но вы, очевидно, не будете менять направление, пока находитесь в воздухе.
В своем грандиозном плане AaParsa хочет использовать пушки для перемещения между городами Шааззляндии, и он может начать перемещения в секунду \(0\). Чтобы использовать их в полной мере, ему нужно знать минимальное количество секунд, необходимое для достижения города \(u\) из города \(v\) с помощью пушек, для каждой пары городов \((u, v)\).
Обратите внимание, что AaParsa может оставаться в любом городе столько, сколько захочет.
Примечание
В первом примере один из возможных путей перехода от \(0\) к \(2\) был бы таким:
- Остаться внутри \(0\) и ничего не делать в течение \(1\) секунды.
- Использовать первую пушку и приземлиться в \(2\) через \(1\) секунду.
Обратите внимание: мы могли бы использовать вторую пушку в
\(0\)-ю секунду, но в этом случае нам потребовалось бы
\(3\) секунды, чтобы достичь города
\(2\).