Діаметри

Обмеження: 4 сек., 512 МіБ

У Зеника та Марічки є дерево: набір з \(n\) вершин та \(n-1\) ребер такий, що з будь-якої вершини можна добратись до будь-якої іншої вершини переходами по ребрах.

Також у них є \(m\) пар вершин \((a_i, b_i)\). Марічка по черзі видаляє вершини з дерева так, щоб усі не видалені вершини також були деревом, тобто кожного разу дівчина видаляє листок. Пара \((a_i, b_i)\) вважається успішною, якщо в якийсь момент вона була одним з діаметрів дерева. Тобто відстань між будь-якою парою не видалених вершин не є більшою за відстань від \(a_i\) до \(b_i\). Якщо в якийсь момент декілька різних пар є одночасно діаметрами, то усі вони є успішними.

Зеник же має \(q\) запитань, кожне з них: чи можуть усі пари від \(l\)-ої до \(r\)-ої, тобто пари \((a_l, b_l)\), \((a_{l+1}, b_{l+1})\), \(\dots\), \((a_r, b_r)\), бути успішними. Допоможіть Зенику відповісти на ці запитання.

Вхідні дані

У першому рядку задано одне ціле число \(n\).

У наступних \(n - 1\) рядках задано по 2 цілих числа, які описують ребра дерева.

У наступному рядку задано єдине ціле число \(m\).

У наступних \(m\) рядках задано по 2 цілих числа \(a_i\) та \(b_i\).

У наступному рядку задано одне ціле число \(q\).

У наступних \(q\) рядках задано по 2 цілих числа \(l_i\) та \(r_i\).

Вихідні дані

Виведіть \(q\) рядків. В \(i\)-му рядку виведіть TAK, якщо можливо, щоб усі пари від \(l_i\) до \(r_i\) були успішними, і NI, якщо ні.

Обмеження

\(1 \le n, m, q \le 2 \cdot 10^5\),

\(1 \le a_i, b_i \le n\), \(a_i \ne b_i\),

\(1 \le l_i \le r_i \le m\).

Приклади