Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Cho một cây N đỉnh, hai người chơi với nhau một trò chơi như sau:

–        Người 1 bắt đầu ở đỉnh u, người 2 bắt đầu ở đỉnh v.

–        Hai người lần lượt chơi luân phiên, ở mỗi bước, người chơi phải di chuyển sang một đỉnh kề với đỉnh đang đứng và không phải là đỉnh người kia đang đứng. Ai đến lượt mà không thể thực hiện nước đi thì thua. Người 1 là người chơi trước.

Với mỗi cặp (u,v), hãy xác định ai là người thắng cuộc.

Input

–        Dòng đầu ghi số N, M - số cặp (u,v). (N, M <= 10⁵)

–        N-1 dòng sau, mỗi dòng ghi 1 cạnh của cây.

–        M dòng sau, mỗi dòng ghi 1 cặp (u,v).

Output

–        M dòng, mỗi dòng ghi 1 số thể hiện người thắng cuộc.

Example

Input:
4 2
1 2
2 3
2 4
3 2
3 4

Output:
2
1