Діаметри

Обмеження: 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$.

Приклади