У Byteland є \(n\) міст, але доріг між ними немає. Проте щодня будуватимуть нову дорогу. Всього буде \(m\) доріг.

Ваше завдання — обробити \(q\) запитів виду:

• "через скільки днів ми зможемо поїхати з міста \(a\) до міста \(b\) вперше?"

Обмеження

• \(1≤n,m,q≤2⋅10^5\)
• \(1≤a,b ≤n\)

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

У першому рядку вхідних даних є три цілі числа \(n\), \(m\) і \(q\): кількість міст, доріг і запитів. Міста пронумеровані цифрами \(1,2,…,n\).

Після цього іде \(m\) рядків, які описують дороги в порядку їх будівництва. У кожному рядку є два цілі числа \(a\) і \(b\): між містами \(a\) і \(b\) буде дорога.

Далі ідуть \(q\) рядків, які описують запити. Кожен рядок містить два цілих числа \(a\) і \(b\): ми хочемо проїхати з міста \(a\) до міста \(b\).

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

Для кожного запиту виведіть кількість днів або −1, якщо це неможливо.

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

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

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

2
-1
4