В країні є \(N\) міст та \(M\) двосторонніх доріг. Спочатку всі дороги зруйновані, і відбудовуються в порядку черги по одній дорозі за день. (Відомо, що після побудови всіх доріг можна буде проїхати між будь-якою парою міст).

\(Q\) пар туристів хочуть відвідати певну кількість міст. Кожен з \(Q\) запитів - три цілих числа \(V1,V2,K\), що означає туристи які знаходяться в місті \(V1\) та \(V2\) хочуть відвідати \(K\) різних міст. Місто зараховується парі туристів, якщо будь-хто з пари відвідав це місто. (Якщо обидва туриста відвідали це місто, воно все одно зараховується лише один раз).

Для кожної пари туристів визначіть, через скільки днів вони зможуть реалізувати свою мрію, відвідати задану кількість міст.

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

В першому рядку два цілих числа \(N,M\) - кількість міст, та кількість доріг (\(3 \le N \le 10^5\)) , (\(N-1 \le M \le 10^5\))
Наступні \(M\) рядків містять по два цілих числа \(Ai,Bi\) - номер міст між якими відбудовується дорога в i-й день.
В наступному рядку міститься число \(Q\) - кількість пар туристів. (\(1 \le Q \le 10^5\)).
В кожному з наступних \(Q\) рядків міститься по три цілих числа \(V1,V2,K\) - що описують пару туристів, які знаходяться в містах \(V1,V2\) і мають на меті відвідати \(K\) міст. (\(V1 \ne V2\)) , (\(3 \le K \le N\))

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

Для кожної пари туристів виведіть в окремому рядку найперший номер дня - після якого вони зможуть відвідати заплановану кількість міст.

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

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

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

1
2
3
1
5
5

Пояснення до прикладу

Після прокладання першої дороги (2 3), перша пара туристів, які знаходяться в містах 2 та 4, зможуть відвідати 3 міста (перший турист зможе відвідати міста 2 і 3, другий турист місто 4).
Аналогічно після прокладання першої дороги, четверта пара туристів, в містах 1 та 3, зможуть відвідати 3 міста. Перший турист місто 1, другий турист міста 3 та 2.
Після прокладання другої дороги (4 5), друга пара туристів (які стоять в містах 2 та 4) зможуть відвідати свої 4 міста (перший турист відвідає міста 2 та 3, другий турист міста 4 та 5).
і т.д