题目描述

有一个包含 $N$ 个节点和 $M$ 条边的有向图 $G$。每个节点编号为 $1$ 到 $N$，每条边编号为 $1$ 到 $M$。对于每个 $i$（$1 \le i \le M$），边 $i$ 从顶点 $u_i$ 指向顶点 $v_i$，并且具有 唯一 的颜色 $c_i$。

一条 路径 定义为边的序列 $e_1, e_2, \cdots, e_{l}$，其中对于每个 $1 \le k < l$，$v_{e_k}$（边 $e_k$ 的终点）与 $u_{e_{k+1}}$（边 $e_{k+1}$ 的起点）相同。我们可以说路径 $e_1, e_2, \cdots, e_l$ 从顶点 $u_{e_1}$ 开始，到顶点 $v_{e_l}$ 结束。注意同一条边可以在一条路径中出现多次。

路径 $e_1, e_2, \cdots, e_l$ 的 颜色序列 定义为 $c_{e_1}, c_{e_2}, \cdots, c_{e_l}$。

考虑图 $G$ 中从顶点 $S$ 到顶点 $T$ 的所有长度不超过 $10^{100}$ 的路径的颜色序列。请编写一个程序，找出这些序列中字典序最小的序列。

输入格式

输入的第一行包含四个以空格分隔的整数 $N$、$M$、$S$ 和 $T$（$1 \le N \le 100,000$，$0 \le M \le 300,000$，$1 \le S \le N$，$1 \le T \le N$，$S \neq T$）。

接下来是 $M$ 行：第 $j$（$1 \le j \le M$）行包含三个以空格分隔的整数 $u_i$、$v_i$ 和 $c_i$（$1 \le u_i, v_i \le N$，$u_i \neq v_i$，$1 \le c_i \le 10^{9}$）；它描述了一条从顶点 $u_i$ 指向顶点 $v_i$ 且颜色为 $c_i$ 的有向边。

图中没有重边，且每条边有唯一的颜色。形式化地说，对于任意 $1 \le i < j \le M$，$c_i \neq c_j$ 且 $(u_i, v_i) \neq (u_j, v_j)$ 成立。

输出格式

如果不存在从顶点 $S$ 到顶点 $T$ 的路径，输出 IMPOSSIBLE（不带引号）。

否则，设 $a_1, a_2, \cdots, a_l$ 是从顶点 $S$ 到顶点 $T$ 的所有长度不超过 $10^{100}$ 的路径的颜色序列中字典序最小的序列。

• 如果 $l \le 10^{6}$，在第一行输出 $a_1, a_2, \cdots, a_l$。每个输出的整数之间应有空格。
• 如果 $l > 10^{6}$，输出 TOO LONG（不带引号）。

3 3 1 3
1 2 1
2 3 7
1 3 5

1 7

3 4 1 3
1 2 1
2 1 2
2 3 7
1 3 5

TOO LONG

2 0 2 1

IMPOSSIBLE

提示

序列 $p_1, p_2, \cdots, p_{n}$ 在字典序上小于另一个序列 $q_1, q_2, \cdots, q_{m}$，当且仅当以下条件之一成立：

• 存在唯一的 $j$（$0 \le j < \min(n, m)$）使得 $p_1 = q_1$，$p_2 = q_2$，$\cdots$，$p_{j} = q_{j}$ 且 $p_{j+1} < q_{j+1}$。
• $n < m$ 且 $p_1 = q_1$，$p_2 = q_2$，$\cdots$，$p_n = q_n$。换句话说，$p$ 是 $q$ 的严格前缀。

翻译由 DeepSeek V3 完成