3551. 城市漫游

【题目描述】

林荫终于有机会与DJ一起逛大街啦,由于DJ是一个文艺少女,她要求林荫规划的路线必须经过城市中每一个节点,并且路线中不能有任何回环.

简单来说,DJ要求路线是城市地图的一棵生成树.

林荫为了尽可能的延长和DJ逛大街的时间,他决定规划出一棵边权和最大的生成树.

现在林荫对此提出了两个问题

1:对于给出的城市地图,满足林荫要求的树是否唯一存在?

2:对于任何一棵满足林荫要求的树,某些点间路径经过的最短边的长度最小值为多少?

对于问题1,仅需要输出YES/NO.

对于问题2,林荫会提出Q组询问,每次询问给入A,B两个点,每次回答在所有满足林荫要求的生成树中从A到B所经过最短边的长度最小值.

记城市地图中节点数目为N,边数为M.

【输入格式】

第一行给入三个正整数:N,M,Q.

下面M行每行三个正整数A,B,C描述从A点到B点存在一条长度为C的双向边.

下面Q行每行两个正整数A,B作为一组询问.

如果A==B,输出0

【输出格式】

第一行输出YES/NO,作为问题1的回答.

下面2-Q+1行每行一个正整数,第i行回答第i-1组询问的答案.

【样例输入】

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

【样例输出】

NO
3
5

【数据规模与约定】

对于30%的数据,保证林荫要求的树唯一存在.

对于70%的数据,M<=1E4,N<=1E3.

对于100%的数据,M<=1E6,N<=1E4.

对于100%的数据,保证边权值小于等于30000,Q<=1e5