Hạo đã bắt đầu nghiên cứu về cấu trúc doanh nghiệp, bao gồm cả hệ thống phân cấp. Anh quan sát các nhân viên và mối quan hệ của họ trong một công ty. Trong trường hợp này, chúng ta chỉ xem xét các mối quan hệ cấp trên-cấp dưới, nghĩa là các mối quan hệ trong đó một nhân viên là cấp trên trực tiếp của một nhân viên khác trong công ty.

Một hệ thống phân cấp là một cấu trúc với \(N\) nhân viên và \(N - 1\) mối quan hệ cấp trên-cấp dưới, trong đó có một người là cấp trên trực tiếp hoặc gián tiếp của tất cả nhân viên. Trong công ty được quan sát, cũng có \(N\) nhân viên và \(N - 1\) mối quan hệ như vậy, nhưng không chắc chắn đây có phải là một hệ thống phân cấp hợp lệ hay không.

Hạo đã yêu cầu bạn giúp trả lời câu hỏi này. Anh ấy đã ghi lại tất cả dữ liệu trong sổ tay của mình. Ngoài ra, trong sổ tay của mình, anh ấy sẽ thực hiện \(Q\) thay đổi vĩnh viễn bằng cách đảo ngược một mối quan hệ cấp trên-cấp dưới sao cho cấp dưới trở thành cấp trên của cấp trên cũ của họ. Sau mỗi thay đổi như vậy, cần phải trả lời cùng một câu hỏi: trạng thái hiện tại có phải là một hệ thống phân cấp hợp lệ không?

Dữ liệu vào

• Trong dòng đầu tiên, có một số nguyên dương \(N\) \((2 \le N \le 3 \times 10^5)\).
• Trong \(N - 1\) dòng tiếp theo, với mỗi \(i = 1, 2, . . . , N - 1\), có một cặp số nguyên \(p_i\) và \(e_i\) \((1 \le p_i, e_i \le N, p_i \neq e_i)\), cho biết \(p_i\) là cấp trên trực tiếp của \(e_i\).
• Trong dòng tiếp theo, có một số nguyên không âm \(Q\) \((0 \le Q \le 10^6)\).
• Trong \(Q\) dòng tiếp theo, có các cặp \(a_i, b_i\) \((1 \le a_i, b_i \le N, a_i \neq b_i)\). Đảm bảo rằng tại thời điểm đó, \(a_i\) sẽ là cấp trên trực tiếp của \(b_i\) hoặc ngược lại.
• Trong dữ liệu test, đảm bảo rằng sẽ có thể đạt được ít nhất một hệ thống phân cấp với một số chuỗi đảo ngược.

Dữ liệu ra

• Trong \(Q + 1\) dòng tiếp theo, với mỗi tình huống đã cho, cần in ra cấu trúc hiện tại có phải là một hệ thống phân cấp hay không, tức là "DA" nếu đúng, hoặc "NE" nếu không (không có dấu ngoặc kép).

Chấm điểm

Input 1

3
1 2
1 3
3
1 2
1 2
1 3

Output 1

DA
DA
DA
DA

Input 2

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

Output 2

DA
NE
DA
DA
NE