codeforces 589H – Tourist Guide(dfs)

H – Tourist Guide

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

Description

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.

Input

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.

Output

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

Input

Output

Input

Output

View Code

 

Posted in ACM

说点什么

您将是第一位评论人!

提醒
wpDiscuz