19258번 - Beyond the Rescue 다국어

Riatla is a little-known member of the Assassins Order (well-known assassins, as you can guess, don't live long). After performing one mission, Riatla faces a problem: the streets of the city are flooded by guards, and he needs a new escape plan from the crime scene.

The city where Riatla is at the moment has a tree-like structure. There are $n$ squares, connected with $n-1$ two-way streets, and there is only one path between every two squares.

Riatla's associates find out that the guards patrol the city in a cyclic route: they choose a sequence of squares $v_1, v_2, \ldots, v_k$, and, after visiting square $v_i$, the guards head to square $v_{i+1}$ (they may be not connected by a direct street, and then the guards go along the shortest path between them). After visiting square $v_k$, they go to square $v_1$, and start their route from the beginning.

Riatla is good at disguising. All the squares in the city are crowded, so the assassin can stay in a square without fear of being noticed by the guards even if the guards are on the same square. On the other hand, there are not many people on the streets, so if the assassin and the guards happen to be on the same street at any moment of time, the guards will shoot the assassin with bows regardless of the distance between them.

You know the plan of the city and how long it takes both the guards and the assassin to pass through every street. You should compute the minimal time that Riatla needs to spend to get from square $s$, where he is now, to square $t$, where his friends are waiting for him. As this time can be rather long, you only need to compute its remainder modulo $998\,244\,353$.

On the first line of input, you are given one integer $t$: the number of test cases. After that, $t$ test cases are given.

The first line of a test case description contains two integers $n$ and $k$: the number of squares in the city and the number of important squares on the guards' path ($2 \le n, k \le 200\,000$).

Each of the next $n-1$ lines contains four integers $u_i$, $v_i$, $c_i$, and $d_i$: the squares connected by streets and the times necessary for the guards and the assassin to walk through each street, respectively ($1 \le u_i, v_i \le n$; $1 \le c_i, d_i \le 10^8$). It is guaranteed that the given graph is a tree.

On the next line, you are given $k$ integers $a_i$: the indices of important squares in the guards' path in the order in which the guards visit them ($1 \le a_i \le n$; $a_i \ne a_{i+1}$; $a_1 \ne a_k$).

On the next line, you are given two integers $s$ and $t$: the starting square of the assassin and the last square of his path ($1 \le s, t \le n$; $s \ne t$).

It is guaranteed that both the sum of $n$ and the sum of $k$ in all the test cases don't exceed $200\,000$.

For each test case, print one number on a separate line: the minimal time the assassin has to spend, modulo $998\,244\,353$. 

If the assassin can't get to his target without being spotted, print $-1$.