基础最短路练习题

题目背景

YSGH 牛逼

题目描述

给定 $n$ 个点 $m$ 条边的简单无向连通图 $G$，边有边权。保证没有重边和自环。

定义一条简单路径的权值为路径上所有边边权的异或和。

保证 $G$ 中不存在简单环使得边权异或和不为 $0$。

$Q$ 次询问 $x$ 到 $y$ 的最短简单路径。

输入格式

第一行三个正整数 $n, m, Q$。

接下来 $m$ 行，一行三个非负整数 $x, y, v$（$1 \le x, y \le n$），表示一条连接 $x, y$，权值为 $v$ 的无向边。保证没有重边和自环。

接下来 $Q$ 行，一行两个正整数 $x, y$（$1 \le x, y \le n$），表示一次询问。

输出格式

$Q$ 行，一行一个整数表示答案。

样例 #1

样例输入 #1

3 2 1
1 2 2
2 3 3
1 3

样例输出 #1

1

提示

对于 $100\%$ 的数据，满足 $1 \le n \le {10}^5$，$1 \le m \le 2n$，$0 \le v < 2^{30}$。