题目描述

Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 $N (1 ≤ N ≤ 300)$ 个站台，分别标记为 $1,2...,N$。所有站台之间有 $M (1 ≤ M ≤ 25,000)$ 条单向路径，第 $i$ 条路经是从站台 $S_i$ 开始，到站台 $E_i$，其中最高的栏的高度为 $H_i (1 ≤ H_i ≤ 1,000,000)$ 。无论如何跑，奶牛们都要跨栏。 奶牛们有 $T (1 ≤ T ≤ 40,000)$ 个训练任务要完成。第 $i$ 个任务包含两个数字 $A_i$ 和 $B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N)$，表示奶牛必须从站台 $A_i$ 跑到站台 $B_i$，可以路过别的站台。奶牛们想找一条路径从站台 $A_i$ 到站台 $B_i$，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

输入格式

第 $1$ 行: 三个整数 $N, M, T$，分别表示站台数、路径数和奶牛的训练任务数量；