Низ графа#6223

Низ графа

1 секунда

64 мегабайти

Дуже легка

Будемо використовувати такі (стандартні) визначення з теорії графів. Нехай $V$ — це непорожня скінченна множина, елементи якої називаються вершинами (або вузлами). Нехай $E \subseteq V \times V$ E \subseteq V \times V, елементи якої називаються ребрами. Тоді $G = (V, E)$ G = (V, E) називається орієнтованим графом.

Нехай $n$ — додатне ціле число, і нехай $p = (e_{1}, \dots, e_{n})$ p = (e_1, \ldots, e_n) — послідовність довжини $n$ ребер $e_{i} \in E$ e_i \in E така, що $e_{i} = (v_{i}, v_{i + 1})$ e_i = (v_i, v_{i+1}) для послідовності вершин $(v_{1}, \dots, v_{n + 1})$ (v_1, \ldots, v_{n+1}). Тоді $p$ називається шляхом від вершини $v_{1}$ v_1 до вершини $v_{n + 1}$ v_{n+1} у $G$ , і кажуть, що $v_{n + 1}$ v_{n+1} досяжна з $v_{1}$ v_1, записуючи $(v_{1} \to v_{n + 1})$ (v_1 \to v_{n+1}).

Ось деякі нові визначення. Вузол $v$ у графі $G = (V, E)$ G = (V, E) називається стоком, якщо для кожного вузла $w$ у $G$ , який досяжний з $v$ , $v$ також досяжна з $w$ .

Дно графа — це підмножина всіх вузлів, які є стоками, тобто

bottom (G) = {v \in V ∣ \forall w \in V : (v \to w) ⟹ (w \to v)} .

\operatorname{bottom}(G) = \{ v \in V \mid \forall w \in V: (v \to w) \implies (w \to v) \}.

Ваше завдання — обчислити дно заданих графів.

Вхідні дані

Вхід містить кілька тестових випадків, кожен з яких відповідає орієнтованому графу $G$ . Кожен тестовий випадок починається з цілого числа $v$ , яке позначає кількість вершин $G = (V, E)$ G = (V, E), де вершини ідентифікуються цілими числами з множини $V = {1, \dots, v}$ V = \{1, \ldots, v\}. Можна вважати, що $1 \leq v \leq 5000$ 1 \le v \le 5000. Далі йдуть невід'ємне ціле число $e$ , а потім $e$ пар ідентифікаторів вершин $v_{1}, w_{1}, \dots, v_{e}, w_{e}$ v_1, w_1, \ldots, v_e, w_e із значенням, що $(v_{i}, w_{i}) \in E$ (v_i, w_i) \in E. Інших ребер, окрім зазначених у цих парах, немає. Останній тестовий випадок супроводжується нулем.

Вихідні дані

Для кожного тестового випадку виведіть дно зазначеного графа в одному рядку. Для цього надрукуйте номери всіх вузлів, які є стоками, у відсортованому порядку, розділені одним пробілом. Якщо дно порожнє, надрукуйте порожній рядок.

Приклади

Приклад 1