В неуказанной Солнечной системе есть $$$N$$$ планет. Космическая правительственная компания недавно наняла космических подрядчиков, чтобы построить $$$M$$$ двусторонних шоссе Hyperspace™, каждое из которых соединяет пару разных планет. Основная цель, заключавшаяся в том, чтобы убедиться, что любая планета может быть достигнута из любой другой планеты, используя только шоссе Hyperspace™, была полностью выполнена. К сожалению, у многих космических подрядчиков были друзья и двоюродные братья в космическом совете директоров компании, поэтому компания решила сделать нечто большее, чем просто соединение всех планет.
Для того, чтобы оправдать траты огромных сумм космических денег на магистрали Hyperspace™, они решили ввести жесткое правило на сети Hyperspace™: для любого путешествия, которое начинается и заканчивается в одной и той же вершине, и посещает каждую планету не более одного раза, каждая пара планет на маршруте должна быть непосредственно связана с помощью шоссе Hyperspace™. Другими словами, для каждого простого цикла индуцированный подграф на множестве планет на нем является кликой.
Вы разрабатываете навигационное приложение Hyperspace™, и ключевая техническая проблема, с которой вы столкнулись — это поиск минимального количества шоссе Hyperspace™, которыми нужно воспользоваться для путешествия из планеты $$$A$$$ на планету $$$B$$$. Поскольку эта задача слишком проста для Bubble Cup, вот более сложная задача: ваша программа должна сделать это для $$$Q$$$ пар планет.
В первой строке входного файла записаны три целых числа $$$N$$$ ($$$1\leq N\leq 100\,000$$$), $$$M$$$ ($$$1\leq M\leq 500\,000$$$) и $$$Q$$$ ($$$1\leq Q\leq 200\,000$$$), описывающих количество планет, количество шоссе Hyperspace™, и количество запросов, соответственно.
Каждая из следующих M строк содержит описание шоссе: шоссе $$$i$$$ описывается двумя числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \leq u_i < v_i \leq N$$$), обозначающими, что $$$u_i$$$ и $$$v_i$$$ соединены с помощью шоссе Hyperspace™. Гарантируется, что сеть планет и шоссе Hyperspace™ всегда является связным простым графом.
Каждая из следующих $$$Q$$$ строк содержит запрос: запрос $$$j$$$ описывается двумя числами $$$a_j$$$ и $$$b_j$$$ $$$(1 \leq a_j < b_j \leq N )$$$, обозначающих, что мы хотим узнать, какое минимальное количество шоссе Hyperspace™ понадобится чтобы добраться из планеты $$$a_j$$$ на планету $$$b_j$$$.
Выведите $$$Q$$$ строк: $$$j$$$-я строка вывода должна содержать минимальное количество шоссе Hyperspace™, которое понадобится чтобы добраться из планеты $$$a_j$$$ на планету $$$b_j$$$.
5 7 2
1 2
1 3
1 4
2 3
2 4
3 4
1 5
1 4
2 5
1
2
8 11 4
1 2
2 3
3 4
4 5
1 3
1 6
3 5
3 7
4 7
5 7
6 8
1 5
2 4
6 7
3 8
2
2
3
3
Граф из второго примера: 
