Xương Rồng Đỉnh

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh, không có khuyên và không có cạnh bội. Đồ thị này là một xương rồng đỉnh (vertex cactus): mỗi đỉnh thuộc về nhiều nhất một chu trình đơn.

Một chu trình đơn là dãy các đỉnh phân biệt $v_1,v_2,\dots ,v_t$ với $t>2$, sao cho có cạnh nối $v_i$ và $v_{i+1}$ với mọi $1\le i<t$, đồng thời có cạnh nối $v_1$ và $v_t$.

Trong bài này, một đường đi từ đỉnh $x$ đến đỉnh $y$ là một dãy đỉnh $v_1=x,v_2,\dots ,v_t=y$ (các đỉnh không nhất thiết phân biệt) sao cho giữa hai đỉnh liên tiếp luôn có cạnh, và mỗi cạnh xuất hiện không quá một lần trên đường đi. Nói cách khác, đỉnh có thể lặp lại nhưng cạnh thì không.

Hai đường đi được coi là khác nhau nếu tập cạnh mà chúng sử dụng khác nhau.

Cho $k$ cặp đỉnh $(x_i,y_i)$. Với mỗi cặp, hãy đếm số đường đi khác nhau bắt đầu tại $x_i$ và kết thúc tại $y_i$. Vì kết quả có thể rất lớn, in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$: có một cạnh nối hai đỉnh $a_i$ và $b_i$.
• Dòng tiếp theo chứa số nguyên $k$: số cặp đỉnh cần truy vấn.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ ($x_i\ne y_i$).

Dữ liệu ra

In ra $k$ dòng, dòng thứ $i$ là số đường đi khác nhau từ $x_i$ đến $y_i$ theo modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le m\le {10}^5$
• $1\le a_i,b_i\le n$
• $1\le k\le {10}^5$
• $1\le x_i,y_i\le n$, $x_i\ne y_i$
• Đồ thị được đảm bảo là xương rồng đỉnh, liên thông, không khuyên, không cạnh bội.

Ví dụ