Андрей — студент ИТМО. Он очень любит гулять по Санкт-Петербургу. Город представляет собой граф из \(n\) перекрёстков и \(m\) улиц, по улицам можно ходить в обе стороны.
После каждой прогулки Андрей оценивает, насколько ритмичной она получилась. Он считает, что у прогулки есть ритм \(k\), если число улиц, которые он прошёл, кратно \(k\). Андрей может проходить по одной и той же улице несколько раз (даже подряд).
Так как ходить одинаковыми маршрутами слишком скучно, ему стало интересно, можно ли начать в перекрёстке \(v\) и закончить в перекрёстке \(u\), чтобы у прогулки был ритм \(k\).
Маршрут — такая последовательность вершин \(a_1, \dots, a_t\), \(t>1\), что соседние вершины соединены ребром (рёбра и вершины могут повторяться). Длина такого маршрута считается равной \(t-1\).
Вы должны помочь ему и ответить на \(q\) запросов.
Формат входных данных
В первой строке даны числа \(n\) и \(m\) — количество перекрёстков и улиц (\(1 \le n \le 10^5,\ 0 \le m \le 10^5\)). В последующих \(m\) строках дано описание графа, по два числа в строке \(v\) и \(u\) — улица, соединяющая вершины \(v\) и \(u\) (\(1 \le v, u \le n\)). В графе могут присутствовать петли и кратные рёбра. В следующей строке дано число \(q\) — количество вопросов (\(1 \le q \le 10^5\)). В последующих \(q\) строках дано по три числа \(v, u, k\) — стартовый и конечный перекрёсток и требуемая ритмичность прогулки (\(1 \le v, u \le n,\ 1 \le k \le 10^6\)).
Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке — ответ на \(i\)-й запрос: Yes, если существует маршрут с ритмичностью \(k\), и No иначе.
| № | Входные данные | Выходные данные |
|
1
|
7 6
1 2
2 3
3 4
4 1
1 5
6 6
5
1 3 2
1 2 2
1 1 6
6 6 5
7 7 2
|
Yes
No
Yes
Yes
No
|