Великий граф з малою сумою ваг ребер

Limits: 2 sec., 256 MiB

Задано граф, який складається з \(n\) вершин та \(m\) ребер. Вага кожного ребра 0 або 1. Сума ваг усіх ребер не перевищує 100.

Також задано \(q\) пар вершин. Ваше завдання — для кожної заданої пари вершин знайти мінімальний шлях між ними, тобто найменшу можливу суму ваг ребер на шляху між вершинами.

Input

У першому рядку задано три цілі числа \(n\), \(m\) та \(q\) — кількість вершин, ребер та запитів відповідно.

У наступних \(m\) рядках задано по три цілі числа \(x_i\), \(y_i\), \(c_i\) — вершини, що сполучає відповідне ребро, а також його вага.

У наступних \(q\) рядках задано по два цілі числа \(u_i\), \(v_i\) — пари вершин, між якими необхідно знайти відстань.

Output

Виведіть \(q\) рядків, по одному цілому числі в кожному — мінімальна відстань між відповідною парою вершин у порядку, в якому вони задані.

Constraints

\(2 \le n \le 2 \cdot 10^5\),

\(1 \le m, q \le 2 \cdot 10^5\),

\(1 \le x_i, y_i, u_i, v_i \le n\),

\(u_i \neq v_i\),

\(0 \le c_i \le 1\),

\(0 \le \sum c_i \le 100\),

у графі немає петель та кратних ребер,

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

Samples

Input (stdin) сopy	Output (stdout) сopy
6 6 5 1 2 0 2 3 0 1 3 1 3 4 1 4 5 0 5 6 1 1 2 1 3 2 4 3 5 1 6	0 0 1 1 2

Notes

У першому запиті потрібно знайти найкращий шлях від 1 до 2. Оскільки існує ребро від 1 до 2 вагою 0, то відповідь 0.

У другому — найкращий шлях від 1 до 3. Оскільки є ребра вагою 0 від 1 до 2 і від 2 до 3, то відповідь також 0.

У третьому — найкращий шлях від 2 до 4. Оптимально піти від 2 до 3 (вага 0) та від 3 до 4 (вага 1), отже відповідь 1.