У столиці однієї невеликої країни дуже складна ситуація. Багатокілометрові пробки буквально паралізували рух у місті, і влада на багатьох вулицях ввела односторонній рух, не аналізуючи, чи можна тепер проїхати з будь-якого місця в місті в будь-яке інше, не порушуючи правила. Транспортна система столиці має \(N\) площ, з'єднаних \(M\) смугами для руху, в тому числі круговими смугами, що проходять по площі. Кожна смуга призначена для руху лише в один певний бік. При цьому на магістралях є смуги, спрямовані як в один, так і в інший бік. По круговій смузі можна рухатися тільки всередині площі і проти годинникової стрілки.

Влада міста на кожній смузі розмістила відеокамеру, тому якщо Інокентій їде зустрічною смугою (за її наявності) або, у разі одностороннього руху, у бік протилежний тому, що показують знаки, то після поїздки проти правил по кожній зі смуг йому доведеться заплатити штраф у розмірі однієї тисячі тугриків цієї країни.

Інокентій, який поспішає купити кахельну плитку зі знижкою, наважився доїхати до магазину у будь-якому разі, навіть якщо для цього доведеться порушувати правила. Але він хоче вибрати такий маршрут руху, сумарний штраф, на якому мінімальний.

Інокентій ще не вирішив, звідки саме і до якого магазину він збирається їхати, тому йому необхідно відповісти на кілька запитань виду «Який мінімальний штраф треба заплатити, щоб дістатися пункту A до пункту B?». Відповідаючи на потреби жителів столиці, відома пошукова система «Індекс» розробляє відповідний сервіс.

Оскільки багато хто з вас рано чи пізно проходитиме співбесіду на роботу в цю фірму, продемонструйте, що ви теж вмієте вирішувати це завдання.

Формат вхідних даних

У першому рядку вхідних даних містяться два числа \(N\) і \(M\) - кількість площ і смуг руху в місті відповідно (\(1 ≤ N ≤ 5000\), \(1 ≤ M ≤ 10 000\)).

Далі містяться описи смуг, якими рух дозволено. Кожна смуга описується номерами двох площ, які з'єднує. Рух дозволено у напрямку від першої із зазначених площ до другої.

У наступному рядку міститься одне число \(K\) — кількість питань у Інокентія (\(1 ≤ K ≤ 10 000\), \(N·K ≤ 2·10^7\)).

У наступних рядках описуються питання, кожне питання описується номерами двох площ, між якими потрібно знайти найдешевший шлях. Шлях необхідно прокласти від першої із зазначених площ до другої.

Формат вихідних даних

Для кожного питання виведіть одне число - шуканий мінімальний розмір штрафу в тисячах тугриків. Якщо шляхи між обраною парою площ не існує, виведіть  -1.

Оцінювання

Тести до цього завдання складаються з чотирьох груп.

• Тест 1. Тест з умови оцінюється в нуль балів.
• Тести 2-10. У тестах цієї групи N не перевищує 10, M не перевищує 20. Ця група оцінюється в 30 балів.
• Тести 11-20. У тестах цієї групи N вбирається у 2000, M вбирається у 3000, K дорівнює 1. Ця група оцінюється в 30 балів.
• Тести 21-47. У тестах цієї групи додаткових обмежень немає. Ця група оцінюється у 40 балів.

Бали за кожну групу тестів ставляться лише за проходження всіх тестів групи.

Приклад вхідних даних

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

Приклад вихідних даних

0
2
0