题目描述

有一棵包含 $n$ 个结点的树，第 $i$ 条边连接结点 $u_i$ 和 $v_i$。

你是一名刺客，初始时刻 $0$ 位于结点 $s$，需要前往结点 $t$ 执行刺杀任务。每个时刻你可以选择：

• 停留在当前结点，等待任意非负实数时间；
• 移动，花费 $d_i$ 的时间沿第 $i$ 条边从一个端点走到另一个端点。移动过程中你始终处于这条边上，不能中途停下。

有一名守卫在树上循环巡逻。他的巡逻路线由 $k$ 个结点

$$x_1,x_2,\ldots,x_k$$

描述。守卫按照

$$x_1\to x_2\to\cdots\to x_k\to x_1\to x_2\to\cdots$$

的顺序不断循环移动。

对于每一段 $x_i\to x_{(i\bmod k)+1}$，守卫都沿树上的唯一路径行进，中途不会在任何结点停留。守卫通过第 $j$ 条边所需的时间为 $c_j$。

**冲突规则：**如果在某个时刻，你和守卫同时出现在同一条边上，包括边的内部但不包括端点，则刺杀任务失败。同时出现在某个结点上不算失败。

求完成刺杀任务，即从 $s$ 到达 $t$，所需的最少时间。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。若无法完成任务，输出 $-1$。

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含两个正整数 $n,k$，分别表示树的结点数和巡逻路线的关键点数。
• 接下来 $n-1$ 行，每行包含四个正整数 $u_i,v_i,c_i,d_i$，描述第 $i$ 条边：该边连接结点 $u_i$ 和 $v_i$，守卫通过该边需要 $c_i$ 时间，刺客通过该边需要 $d_i$ 时间。
• 接下来一行包含 $k$ 个正整数 $x_1,x_2,\ldots,x_k$，表示守卫巡逻路线的关键点序列。
• 最后一行包含两个正整数 $s,t$，表示刺客的起点和终点。

输出格式

对于每组测试数据，输出一行一个整数：

• 若刺客可以完成任务，输出最少时间对 $998244353$ 取模后的结果；
• 若刺客无论如何都无法完成任务，输出 $-1$。

样例 1

输入

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

输出

3

解释

树结构中，结点 $2$ 为中心，分别连接结点 $1,3,4$。

守卫巡逻

$$3\to4\to3\to\cdots,$$

其实际路径为

$$3\to2\to4\to2\to3\to\cdots.$$

因此守卫只经过边 $(2,3)$ 和边 $(2,4)$，从不经过边 $(1,2)$。

刺客只需经过边 $(1,2)$，耗时为 $d_1=3$。在时刻 $0$ 直接出发，并于时刻 $3$ 到达，因此答案为 $3$。

样例 2

输入

1
2 2
1 2 3 5
1 2
1 2

输出

-1

解释

树中只有唯一的一条边 $(1,2)$，其参数为 $c=3,d=5$。

守卫巡逻

$$1\to2\to1\to\cdots,$$

周期为 $P=6$。守卫在这条边上的占用时段为

$$(0,3)\cup(3,6),$$

仅在时刻 $0,3,6,\ldots$ 处于端点上。

刺客需要一段长度为 $5$ 的连续安全时间窗口才能通过该边，但最长安全间隙长度仅为 $0$，因此无法完成任务，答案为 $-1$。

样例 3

输入

1
3 2
1 2 1 1
2 3 1 1
1 3
1 3

输出

4

解释

树是一条链 $1-2-3$，并且所有 $c_i=d_i=1$。守卫巡逻

$$1\to3\to1\to\cdots,$$

周期为 $P=4$。在一个周期内，守卫所在位置如下：

时段	守卫所在边	方向
$(0,1)$	边 $(1,2)$	$1\to2$
$(1,2)$	边 $(2,3)$	$2\to3$
$(2,3)$		$3\to2$
$(3,4)$	边 $(1,2)$	$2\to1$

一种最优方案如下：

• 在时刻 $1$ 从结点 $1$ 出发，经过边 $(1,2)$，于时刻 $2$ 到达结点 $2$；
• 等待到时刻 $3$，经过边 $(2,3)$，于时刻 $4$ 到达结点 $3$。

因此答案为 $4$。

数据范围

对于全部数据：

• $1\le T\le 10$；
• $2\le n\le 2\times10^5$，$2\le k\le 2\times10^5$；
• $1\le u_i,v_i\le n$，输入保证这些边构成一棵树；
• $1\le c_i,d_i\le 10^8$；
• $1\le x_i\le n$，且 $x_i\ne x_{(i\bmod k)+1}$；
• $1\le s,t\le n$，且 $s\ne t$；
• 在同一个测试点中，所有测试数据的 $\sum n$ 和 $\sum k$ 均不超过 $2\times10^5$。

记 $\operatorname{dist}(u,v)$ 表示 $u$ 到 $v$ 的树上路径所经过的边数，$\operatorname{path}(u,v)$ 表示该路径的边集。

子任务

子任务编号	分值	特殊限制
1	5	$s$ 和 $t$ 在树上相邻，即二者之间恰好有一条边直接相连
2	10	$n\le50$，$k\le50$，$c_i\le20$，$d_i\le20$
3	15	$k=2$
4		守卫一轮巡逻经过的总边数不超过 $5000$，即 $\displaystyle\sum_{i=1}^{k}\operatorname{dist}\!\left(x_i,x_{(i\bmod k)+1}\right)\le5000$
5	10	守卫一轮巡逻中，经过的边与 $s$ 到 $t$ 路径上的边的交集大小之和不超过 $5000$，即 $\displaystyle\sum_{i=1}^{k}\left
6	15	树是一条链，即存在一种编号方式使边恰好连接 $i$ 和 $i+1$（$1\le i\le n-1$）
7	30	无特殊限制