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