Шляхи між усіма
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) | Output (stdout) |
|---|---|
| 4 5 1 2 2 3 3 4 4 1 1 3 | TAK |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 4 1 3 1 2 2 3 1 3 | NI |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|