7773: BZOJ3773:ICBM
Memory Limit:64 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
J国有N个大城市,城市之间建立了发达的高速路网。在J国,两个城市之间的高速公路都是直线连接的,且没有两条高速公路在端点城市以外的地方相交。另外,J国已经做好了战争规划,使得在任意一个城市或任意一个道路被摧毁的情况下,整个国家的路网依然能够畅通。 K国打算闪电突击J国,他们储备了大量的ICBM(Intercontinental Ballistic Missile,洲际弹道导弹),一枚导弹能够摧毁J国的一个城市。为了让闪击更有战略意义,K国的战争领导层提出了L个方案,每个方案是一个序列(a1,a2,...,an),保证a1-a2,a2-a3,...,an-1-an,an-a1之间都有高速公路连接,且没有一个城市在序列上重复出现。这个方案的实施方法就是部署ICBM摧毁序列表示的环内所有的城市(包括落在环上的)。 现在战争领导层打算统计每个方案的导弹消耗。这个任务就交给你了。
输入格式
第一行两个数N,M,表示J国的城市数量以及高速路数量。 接下来M行,每行两个数x,y,表示x和y之间有一条高速路连接。保证没有重边和自环。 接下来N行,每行两个整数Xi,Yi,表示第I个城市的平面坐标。(坐标绝对值<=10^9) 接下来一行L,表示方案个数。 接下来L行,每行以一个数k(k>=3)开头,接下来k个数a1,a2,a3,...,ak,表示一个方案。
输出格式
L行,每行一个数,表示对应方案需要的导弹数量。
样例输入
5 8 5 1 5 2 5 3 5 4 4 1 1 2 3 2 3 4 0 0 2 0 2 2 0 2 1 1 1 4 4 3 2 1
样例输出
5
提示
N<=33333,L<=30000,S<=100000
题目来源
没有写明来源