Cho một cây bao gồm ~n~ đỉnh và ~n-1~ cạnh. Với mỗi cạnh theo thứ tự đầu vào, tìm số đường đi đơn phân biệt đi qua cạnh đó modulo 67.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~ là số lượng đỉnh của cây.

~n-1~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~u_i~, ~v_i~ là cạnh thứ ~i~ của cây.

Output

In ra ~n-1~ số, số thứ ~i~ là số lượng đường đi đơn phân biệt đi qua cạnh thứ ~i~ của cây theo thứ tự nhập vào modulo 67.

Scoring

Sample Input 1

3
1 2
2 3

Sample Output 1

2 2