Thương Nhân Tham Lam

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh. Giữa hai đỉnh bất kỳ có không quá một cạnh nối trực tiếp.

Có $k$ thương nhân. Thương nhân thứ $i$ có kho hàng ở đỉnh $s_i$ và cửa hàng ở đỉnh $l_i$. Một cạnh được gọi là quan trọng đối với thương nhân $i$ nếu việc xóa cạnh đó khiến không còn đường đi từ $s_i$ đến $l_i$.

Với mỗi thương nhân, hãy đếm số cạnh quan trọng đối với người đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i,b_i$ ($1\le a_i,b_i\le n$, $a_i\ne b_i$) — hai đầu mút của một cạnh.
• Dòng tiếp theo chứa số nguyên $k$.
• $k$ dòng cuối, mỗi dòng chứa hai số nguyên $s_i,l_i$ ($1\le s_i,l_i\le n$).

Dữ liệu ra

In ra $k$ dòng. Dòng thứ $i$ là số cạnh quan trọng đối với thương nhân $i$.

Ràng buộc

• $1\le n,m,k\le {10}^5$
• Đồ thị liên thông, không có cạnh bội.
• Cho phép $s_i=l_i$ (khi đó đáp án là $0$).

Ví dụ