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

Обмеження: 2 сек., 256 МіБ

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

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

\(1 \le u, v \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 5 1 2 2 3 3 4 4 1 1 3	TAK

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 4 1 3 1 2 2 3 1 3	NI