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