配点 : 100 点
問題文
在顶部 在 1 从 N 一边 1 从 M 它有多个 N 頂点 M 给出了一个简单连接的无向边图。侧面 i 是顶点 u_i 和顶点 询问 v_i 和一个整数 A_i 已经写好了。
现在,顶点 1 Nitako 有一根维也纳香肠。 Tako-san 的维也纳有腿 1 我有这本书。 Tako-san Wiener 通过重复以下动作到达顶部。 我正在考虑前往 N 。
- 添加连接到当前顶点的边 1 选择一项。选定的边作为边 i 。
- 找出Tako-san Wiener当前的腿数。 x 作为一本书, 满足x \le y 和 y\ \mathrm{OR}\ A_i = A_i 的整数 选择 y 。还有腿的数量 y 为书本添加了侧面 i 。 表示
这里 如果你知道 a\ \mathrm{OR}\ b 表示 a 和 我讨厌 b 的按位逻辑和。
Tako的维也纳是顶级 判断是否可以到达 N ,如果可以则第一次设置顶点 当 Tako-san Wiener 达到 N 时,求出它的最小和最大可能的腿数。
制約
- 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 \lt 2^{30}
- 作为输入给出的图是简单连接的
- 输入全为整数。
入力
输入是按以下格式从标准输入给出的。
N\ M u_1\ v_1\ A_1 u_2\ v_2\ A_2 \vdots u_M\ v_M\ A_M
出力
Tako 的维也纳首次登顶
按顺序输入 tako-san 香肠达到 N 时可能的最小和最大腿数,并用空格分隔。
在 1 行输出。
无论你如何表现,你都会处于巅峰
如果您无法到达 N 如果你无法到达 -1 -1 。
入力例 1
4 4 1 2 6 2 3 1 3 4 4 1 4 7
出力例 1
1 7
起初,Tako-san 的维纳有腿。 1 在书的状态下,顶点 我在 1 。例如,您可以按如下方式移动。 选择
- 辺 4 ,y = 1 那么腿的数量是 转至 1 在书的状态下,顶点 我在 4 。
这样移动会增加腿的数量。 1 本书顶部 您可以前往 4 。您也可以如下移动。 您可以前往
- 辺 4 ,y = 7 那么腿的数量是 转至 7 在书的状态下,顶点 我在 4 。
这样移动会增加腿的数量。 7 本书顶部 您可以前往 4 。这是顶部 这是在达到 4 时如何实现最小和最大柱数。
入力例 2
4 4 1 2 100 1 3 200 2 4 1 3 4 5
出力例 2
-1 -1
入力例 3
6 10 3 5 1 1 5 2 1 3 3 3 4 4 1 6 5 4 6 6 5 6 7 2 4 8 2 5 9 1 2 10
出力例 3
1 7