Một đất nước có ~n~ thành phố được đánh số từ 1 tới ~n~. Có ~m~ con đường cao tốc hai chiều được đánh số từ 1 tới ~m~, mỗi con đường nối trực tiếp hai thành phố phân biệt. Các con đường này đảm bảo từ một thành phố bất kỳ có thể đi đến một thành phố bất kỳ khác hoặc trực tiếp hoặc gián tiếp thông qua các các con đường khác. Giữa hai thành phố có thể có nhiều hơn một con đường nối trực tiếp.

Theo kế hoạch của Ban quản lý đường bộ, sắp tới mỗi đợt sẽ kiểm tra định kì một trong ~m~ con đường cao tốc. Trong thời gian kiểm tra người dân sẽ bị cấm ra, vào con đường này. Một con đường được xem là trọng yếu đối với hai thành phố ~u~ và ~v~ khi và chỉ khi mọi cách đi từ ~u~ đến ~v~ đều phải đi qua con đường đó (không được phép đi qua con đường đang kiểm tra). Lưu ý là nếu không có đường đi nào từ ~u~ đến ~v~ thì đối với hai thành phố này không có con đường nào là trọng yếu. Công ty BMAP quyết định xây dựng một phần mềm tra cứu giúp người dân nơi đây tìm xem, với một cặp thành phố ~(u,v)~, nếu một con đường được chọn để kiểm tra thì sẽ có những con đường nào là trọng yếu trong số ~m-1~ con đường còn lại.

Yêu cầu: Bạn hãy giúp công ty BMAP đưa ra kết quả tra cứu cho người dân.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~ và ~m~ (~n,m \geq 2~);
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo (~1\leq i \leq m~) chứa 2 số nguyên dương ~u~ và ~v~ (~u,v \leq n; u\neq v~) cho biết đường cao tốc thứ ~i~ nối trực tiếp hai thành phố ~u~ và ~v~;
• Dòng tiếp theo chứa một số nguyên dương ~q~ là số lượng truy vấn;
• Dòng thứ ~j~ trong số ~q~ dòng tiếp theo (~1\leq j \leq q~) chứa 3 số nguyên dương ~k~, ~u~ và ~v~ (~k \leq m; u,v \leq n; u\neq v~) mô tả truy vấn thứ ~j~ nếu con đường ~k~ đang trong đợt kiểm tra thì cần tìm số con đường trọng yếu giữa hai thành phố ~u~ và ~v~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra ~q~ dòng, dòng thứ ~j~ (~1\leq j\leq q~) ghi một số duy nhất là tổng số con đường trọng yếu tìm được đối với truy vấn thứ ~j~ trong dữ liệu vào.

Giới hạn

• Subtask 1 (15 điểm): ~n,m,q\leq 500~;
• Subtask 2 (15 điểm): ~n,m,q\leq 5000~;
• Subtask 3 (20 điểm): ~n,m,q\leq 200000~, ~k=1~ trong mọi truy vấn;
• Subtask 4 (20 điểm): ~n,m,q\leq 200000~, ~u=1~ và ~v=2~ trong mọi truy vấn;
• Subtask 5 (30 điểm): ~n,m,q\leq 200000~.

Sample input

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

Sample output

1
0
1

Hình minh họa ví dụ