AT_KeioPC2025_h Takosan Takusan

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。每条边 $i$ 连接顶点 $u_i$ 和顶点 $v_i$，并且有一个整数 $A_i$ 标记。 现在，有一个“章鱼小香肠”在顶点 $1$。章鱼小香肠一开始有 $1$ 条腿。它打算通过反复执行以下操作前往顶点 $N$： 1. 选择当前顶点连接的一条边，设其编号为 $i$。 2. 记当前腿数为 $x$。选择一个整数 $y$，使得 $x \le y$ 且 $y\ \mathrm{OR}\ A_i = A_i$ 成立（$\mathrm{OR}$ 表示按位或运算）。然后将腿的数量增加到 $y$，并经过边 $i$ 移动到另一端的顶点。 请判断章鱼小香肠是否能够到达顶点 $N$。如果可以，输出它首次到达顶点 $N$ 时腿的本数可能的最小值和最大值（以空格隔开，输出一行）。如果无论怎样都无法到达顶点 $N$，请输出 `-1 -1`。

输入按以下格式从标准输入读入： > $N\ M$ > $u_1\ v_1\ A_1$ > $u_2\ v_2\ A_2$ > $\vdots$ > $u_M\ v_M\ A_M$

输出一行，依次输出章鱼小香肠首次到达顶点 $N$ 时腿数的最小值和最大值，用空格隔开。如果无法到达，则输出 `-1 -1`。

### 样例说明 1 一开始，章鱼小香肠在顶点 $1$，有 $1$ 条腿。例如，可以按照以下方式移动： - 选择边 $4$，取 $y=1$，则以 $1$ 条腿到达顶点 $4$。 这样可以以 $1$ 条腿到达顶点 $4$。或者，还可以： - 选择边 $4$，取 $y=7$，则以 $7$ 条腿到达顶点 $4$。 这样可以以 $7$ 条腿到达顶点 $4$。这就是到达顶点 $4$ 时腿数最小值和最大值的实现方式。 ### 数据范围 - $2 \le N \le 2 \times 10^5$ - $1 \le M \le 2 \times 10^5$ - $1 \le u_i, v_i \le N$ - $0 \le A_i < 2^{30}$ - 输入图为简单连通无向图 - 所有输入均为整数 由 ChatGPT 5 翻译