Thầy giáo dạy giáo dục thể chất tại trường chuyên XYZ đang cần tổ chức cuộc thi chạy cho học sinh, biết địa bàn thành phố là đồ thị vô hướng dạng cây gồm ~N~ đỉnh và ~N-1~ cạnh.

Do cần giám sát, đảm bảo an toàn, giáo sư đã nhờ một chuyên gia khoa học máy tính thiết kế một camera để giám sát trên đoạn đường chạy. Chuyên gia đã đưa cho thầy giáo ~Q~ phương án. Mỗi phương án là bộ ~3~ số ~u,v,w~ trong đó ~u,v~ là điểm đầu, cuối của đoạn đường chạy, ~w~ là vị trí đặt camera.

Bạn hãy giúp xem chuyên gia đã thực hiện đúng yêu cầu của thầy giáo đặt ra chưa.

Input

Vào từ file MARATHON.INP:

• Dòng đầu chứa 2 số nguyên dương là số đỉnh của đồ thị ~N\ (N \le 10^5)~, và số phương án chọn đường chạy ~Q\ (Q \le 10^5)~.
• Các dòng tiếp theo thể hiện cạnh của đồ thị.
• Các dòng sau đó là ~Q~ phương án, cấu trúc như trên.

Output

Ghi ra tệp MARATHON.OUT:

• Gồm ~Q~ dòng, nếu phương án đảm bảo việc lắp camera trên đường chạy thì in ra ~1~, ngược lại in ra ~0~.

Sample Input 1

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

Sample Output 1

1
1
0