查房

题目背景

答疑请到: https://www.luogu.org/discuss/show?postid=79498 $sqn$是个电子游戏爱好者,但很遗憾的是,他的母上大人没收了他的手机。为了过一把游戏瘾,$sqn$到各个$oier$的宿舍借手机玩......

题目描述

当然,这是一件风险很大的事,因为van恶的静静和晶晶会定时查房,被抓到可就惨了。当然$oier$们不会束手就擒,他们组织了一个反查房联盟。这个联盟由$n$个宿舍(点)组成,某些宿舍之间有边权为1无向边连接,共有$n-1$条无向边。每个点都有一个概率$k_i$,表示在颓废的几率为$k_i$。如果老师查到某个房间,而这个房间的人在学习,他就会发出警报,距离他1的人收到警报后都会在下一时刻无条件停止颓废,之后恢复原状态,如果查到在颓废的人,则那个人不会发出警报而是GG(可以当作这个人死了,再也不会发出信号)。静静和晶晶一起行动,查一遍房间。$sqn$只会在$ztz11$,$AK$爷,$floatiy$的房间里颓废,他想知道,在哪个房间里颓废被查到几率最小?当然,由于他在颓废,所以自然不可能算几率啦,他将这个问题交给了你,请你帮他来解决这个问题

输入输出格式

输入格式


第一行,两个数字$n$,$m$,表示房间总数 和查房次数 第二行,3个数字$a,b,c$,分别表示 $ztz11$,$AK$爷和$floatiy$的房间号 下面$m$行,每行第一个数字$k$,表示当前时刻老师们要查几间房,后面$k$个数字,表示静静和晶晶要查的房间号 下面$n-1$行,每行$2$个数,表示会相互发出警报的两个人 最后一行,$n$个数,表示每个人颓废的几率

输出格式


第一行,一个整数,表示$sqn$应该去的最佳的房间,如果几率相同,请按$ztz11>AK>floatiy$的优先级输出 第二行,一个4位小数,表示$sqn$安全颓废的几率

输入输出样例

输入样例 #1

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

输出样例 #1

1
0.9940

说明

对于 $30$% 的数据,$n,m<=10$, 对于另 $10$% 的数据,$k=1$ 对于 $100$% 的数据,$1<=m,n<=1000000$,确保每个人被且仅被查一次 感谢@XiaoX,@Monster_qi帮助出数据&验题