Background

For questions, please go to: https://www.luogu.org/discuss/show?postid=79498.

$sqn$ is a video game fan, but unfortunately his mom took away his phone. To satisfy his desire to play games, $sqn$ borrows phones from different $oier$ dorm rooms to play games......

Problem Description

Of course, this is very risky, because the evil Jingjing and Jingjing will inspect the rooms regularly, and getting caught would be terrible. Of course, the $oier$s will not just give up, so they organized an anti-inspection alliance.

This alliance consists of $n$ dorm rooms (nodes). Some dorm rooms are connected by undirected edges with weight $1$, and there are $n-1$ undirected edges in total. Each node has a probability $k_i$, meaning the probability of being slacking off is $k_i$.

If a teacher inspects a room and the person in that room is studying, they will raise an alarm. After a person at distance $1$ receives the alarm, they will unconditionally stop slacking off at the next moment, and then return to their original state. If the teacher inspects someone who is slacking off, then that person will not raise an alarm and will instead be GG (you can treat it as the person is dead and will never send signals again).

Jingjing and Jingjing act together and inspect the rooms once. $sqn$ will only slack off in the rooms of $ztz11$, Grandpa $AK$, and $floatiy$. He wants to know: in which room is the probability of being caught while slacking off the smallest?

Of course, since he is slacking off, he cannot calculate the probability himself. He leaves this problem to you. Please help him solve it.

Input Format

The first line contains two integers $n$, $m$, representing the total number of rooms and the number of inspections.

The second line contains three integers $a, b, c$, representing the room numbers of $ztz11$, Grandpa $AK$, and $floatiy$.

The next $m$ lines: the first number is $k$, meaning how many rooms the teachers will inspect at the current moment; the following $k$ numbers are the room numbers that Jingjing and Jingjing will inspect.

The next $n-1$ lines: each line contains $2$ numbers, indicating two people who can send alarms to each other.

The last line contains $n$ numbers, representing each person's probability of slacking off.

Output Format

The first line outputs one integer, indicating the best room that $sqn$ should go to. If the probabilities are the same, output according to the priority $ztz11 > AK > floatiy$.

The second line outputs a number with $4$ digits after the decimal point, representing the probability that $sqn$ can slack off safely.

3 2
1 2 3
2 2 3
1 1
1 2
1 3
0.3 0.1 0.2

1
0.9940

Hint

For $30\%$ of the testdata, $n, m \le 10$.

For another $10\%$ of the testdata, $k = 1$.

For $100\%$ of the testdata, $1 \le m, n \le 1000000$, and it is guaranteed that everyone is inspected once and only once.

Thanks to @XiaoX and @Monster_qi for helping provide data & validate the problem.

Translated by ChatGPT 5