codeforces 589H – Tourist Guide(dfs)

2015年10月27日 0 作者 CrazyKK
H – Tourist Guide

Time Limit:2000MS     Memory Limit:524288KB     64bit IO Format:%I64d & %I64u


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 ai and bi(1 ≤ ai, bi ≤ n) — meaning that cities ai and bi are connected by a bidirectional road. It is guaranteed that ai and bi 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 “tv1v2 … vt + 1“, where t is a number of roads in a route and v1,  v2, …, vt + 1 — cities listed in the order they are visited on the route.

If there are multiple answers print any of them.

Sample Input





View Code