Шляхи між усіма

Limits: 2 sec., 256 MiB

У Зеника є орієнтований граф із $n$ вершин та $m$ ребер. Вершини пронумеровані цілими числами від 1 до $n$ включно.

Марічці стало цікаво, чи для кожної пари вершин $i$ та $j$ ($1 \le i, j \le n$) існує орієнтований шлях (використовуючи довільну кількість ребер, можливо нульову) від вершини $i$ до вершини $j$? Допоможіть їм визначити це.

Input

У першому рядку задано два цілих числа $n$ та $m$ — кількість вершин та орієнтованих ребер.

У наступних $m$ рядках задано пари чисел $u$ та $v$, кожна з яких означає, що існує ребро $u \rightarrow v$.

Output

Виведіть TAK, якщо між усіма впорядкованими парами вершин існує шлях, або NI в протилежному випадку.

Constraints

$1 \le n, m \le 2 \cdot 10^5$,

$1 \le u, v \le n$.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 5 1 2 2 3 3 4 4 1 1 3	TAK

Input (stdin) сopy	Output (stdout) сopy
3 4 1 3 1 2 2 3 1 3	NI