Problem description

Bajtoławska Firma Samochodowa (w skrócie BFS) obsługuje n przystanków autobusowych na terenie całej Bajtoławy. Sieć połączeń jest bardzo przemyślana, istnieje bowiem m połączeń rozłożonych po terenie całego miasta tak równomiernie, że przejazd każdym z nich zajmuje dokładnie jeden czasu¹, a z każdego przystanku da się, być może wieloma połączeniami, dojechać do każdego innego. Połączenia te obsługiwane są przez $\frac{n(n-1)}{2}$ linii, po jednej na każdą parę przystanków, z których każda przejeżdża po pewnej najkrótszej trasie pomiędzy przystankiem początkowym i końcowym. Okazuje się jednak, że nawet najbardziej przemyślane trasy nie są w stanie powstrzymać BFSa przed generowaniem olbrzymiej ilości spóźnień. By zrekompensować je pasażerom, zarząd zdecydował wypuścić aplikację ułatwiającą korzystanie z autobusów. Jedną z jej ważnych funkcjonalności, której napisanie zlecono Tobie, ma być podawanie najkrótszego czasu przejazdu pomiędzy dwoma wskazanymi przystankami, przy założeniu, że autobus będzie jechał bez opóźnienia.

Wejście

W pierwszej linii wejścia znajdują się trzy liczby całkowite n m i q oznaczjące kolejno liczbę przystanków, liczbę połączeń, oraz liczbę zapytań o trasy pomiędzy dwoma przystankami. W następnych m liniach wejścia znajduje się opis sieci połączeń autobusowych. W każdej z nich znajdują się dwie liczby różne całkowite 1 ≤ a, b ≤ n oznaczające, że pomiędzy przystankami a i b istnieje dwukierunkowe połączenie, którym przejazd zajmie jeden czasu. Na wejściu nigdy nie pojawią się dwie takie same pary. W kolejnych q liniach wejścia znajdują się opisy kolejnych zapytań. W każdym z nich znajdują się dwie liczby całkowite 1 ≤ v, u ≤ n, oznaczające, że zapytanie dotyczy przejazdu pomiędzy przystankami v i u.

Wyjście

Wyjście składa się z q linii. W i-tej z nich znajduje się odpowiedź na pytanie o to ile wynosi minimalny czas przejazdu pomiędzy przystankami podanymi w i-tym zapytaniu.

Ograniczenia

We wszystkich testach zachodzi zależność 2≤ n, m ≤ 2000, 1 ≤ q ≤ 10⁶
Dodatkowo w testach wartych 40% punktów zachodzi zależność q ≤ 2000
W innych testach wartych 15% punktów zachodzi zależność n ≤ 3

Przykład

4 4 2
1 2
3 1
3 4
2 4
1 3
1 4

1
2