Tourist Guide
题意翻译
有一个$n$个点$m$条边的图,指定$k$个点为关键点。
每次你可以选择两个未被选择过的在图上联通的关键点,选择它们之间的一条简单路径,将这条路径上的所有边删除。
你需要输出最多能选多少对点,并且输出每对点你删除路径长度和这条路径经过的点。
题目描述
It is not that easy to create a tourist guide as one might expect. A good tourist guide should properly distribute flow of tourists across the country and maximize the revenue stream from the tourism. This is why there is a number of conditions to be met before a guide may be declared as an official tourist guide and approved by Ministry of Tourism.
Ministry of Tourism has created a list of $ k $ remarkable cities out of $ n $ cities in the country. Basically, it means that in order to conform to strict regulations and to be approved by the ministry a tourist guide should be represented as a set of routes between remarkable cities so that the following conditions are met:
- the first and the last city of every route are distinct remarkable cities,
- each remarkable city can be an endpoint of at most one route,
- there is no pair of routes which share a road.
Please note that a route may pass through a remarkable city. Revenue stream from the tourism highly depends on a number of routes included in a tourist guide so the task is to find out a set of routes conforming the rules of a tourist guide with a maximum number of routes included.
输入输出格式
输入格式
The first line contains three integer numbers $ n,m,k $ $ (1<=n<=50000,0<=m<=50000,1<=k<=n) $ — the number of cities in the country, the number of roads in the country and the number of remarkable cities correspondingly.
Each of the following $ m $ lines contains two integer numbers $ a_{i} $ and $ b_{i} $ $ (1<=a_{i},b_{i}<=n) $ — meaning that cities $ a_{i} $ and $ b_{i} $ are connected by a bidirectional road. It is guaranteed that $ a_{i} $ and $ b_{i} $ are distinct numbers and there is no more than one road between a pair of cities.
The last line contains $ k $ distinct integer numbers — a list of remarkable cities. All cities are numbered from 1 to $ n $ .
输出格式
The first line of the output should contain $ c $ — the number of routes in a tourist guide. The following $ c $ lines should contain one tourist route each. Every route should be printed in a form of " $ t $ $ v_{1} $ $ v_{2} $ ... $ v_{t+1} $ ", where $ t $ is a number of roads in a route and $ v_{1},v_{2},...,v_{t+1} $ — cities listed in the order they are visited on the route.
If there are multiple answers print any of them.
输入输出样例
输入样例 #1
6 4 4
1 2
2 3
4 5
5 6
1 3 4 6
输出样例 #1
2
2 1 2 3
2 4 5 6
输入样例 #2
4 3 4
1 2
1 3
1 4
1 2 3 4
输出样例 #2
2
1 1 2
2 3 1 4