Правила дорожнього руху
У столиці однієї невеликої країни склалася складна ситуація. Багатокілометрові затори буквально паралізували рух у місті, і влада запровадила односторонній рух на багатьох вулицях, не перевіривши, чи можна тепер дістатися з будь-якої точки міста в іншу, не порушуючи правил. Транспортна система столиці складається з N площ, з'єднаних M смугами для руху, включаючи кругові смуги, що проходять по площі. Кожна смуга призначена для руху лише в одному напрямку. На магістралях є смуги, спрямовані як в один, так і в інший бік. По круговій смузі можна рухатися тільки всередині площі і лише проти годинникової стрілки.
Влада міста встановила відеокамери на кожній смузі, тому якщо Іннокентій їде по зустрічній смузі (за її наявності) або, у випадку одностороннього руху, у напрямку, протилежному вказаному знаками, то після поїздки проти правил по кожній із смуг йому доведеться заплатити штраф у розмірі однієї тисячі тугриків цієї країни.
Іннокентій, який поспішає купити кахельну плитку зі знижкою, вирішив дістатися до магазину в будь-якому випадку, навіть якщо для цього доведеться порушувати правила. Але він хоче обрати такий маршрут, на якому сумарний штраф буде мінімальним.
Іннокентій ще не вирішив, звідки саме і в який магазин він збирається їхати, тому йому необхідно відповісти на кілька запитань типу: Який мінімальний штраф треба заплатити, щоб дістатися з пункту A в пункт B? Відповідаючи на потреби жителів столиці, відома пошукова система Індекс розробляє відповідний сервіс.
Оскільки багато хто з вас рано чи пізно буде проходити співбесіду на роботу в цю фірму, продемонструйте, що ви теж вмієте розв'язувати цю задачу.
Вхідні дані
У першому рядку вхідних даних містяться два числа N і M — кількість площ і смуг руху в місті відповідно (1 ≤ N ≤ 5000, 1 ≤ M ≤ 10000). Далі містяться описи смуг, по яких рух дозволено. Кожна смуга описується номерами двох площ, які вона з'єднує. Рух дозволено в напрямку від першої з указаних площ до другої.
У наступному рядку міститься одне число K — кількість запитань у Іннокентія (1 ≤ K ≤ 10000, N·K ≤ 2·10^7). У наступних рядках описуються запитання, кожне запитання описується номерами двох площ, між якими потрібно знайти найдешевший шлях. Шлях необхідно прокласти від першої з указаних площ до другої.
Вихідні дані
Для кожного запитання виведіть одне число — шуканий мінімальний розмір штрафу в тисячах тугриків. У випадку, якщо шляху між обраною парою площ не існує, виведіть -1.