В неуказанной Солнечной системе есть \(N\) планет. Космическая правительственная компания недавно наняла космических подрядчиков, чтобы построить \(M\) двусторонних шоссе Hyperspace™, каждое из которых соединяет пару разных планет. Основная цель, заключавшаяся в том, чтобы убедиться, что любая планета может быть достигнута из любой другой планеты, используя только шоссе Hyperspace™, была полностью выполнена. К сожалению, у многих космических подрядчиков были друзья и двоюродные братья в космическом совете директоров компании, поэтому компания решила сделать нечто большее, чем просто соединение всех планет.
Для того, чтобы оправдать траты огромных сумм космических денег на магистрали Hyperspace™, они решили ввести жесткое правило на сети Hyperspace™: для любого путешествия, которое начинается и заканчивается в одной и той же вершине, и посещает каждую планету не более одного раза, каждая пара планет на маршруте должна быть непосредственно связана с помощью шоссе Hyperspace™. Другими словами, для каждого простого цикла индуцированный подграф на множестве планет на нем является кликой.
Вы разрабатываете навигационное приложение Hyperspace™, и ключевая техническая проблема, с которой вы столкнулись — это поиск минимального количества шоссе Hyperspace™, которыми нужно воспользоваться для путешествия из планеты \(A\) на планету \(B\). Поскольку эта задача слишком проста для Bubble Cup, вот более сложная задача: ваша программа должна сделать это для \(Q\) пар планет.