Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

H. Tourist Guide

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIt 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 *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*.

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 "*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.

Examples

Input

6 4 4

1 2

2 3

4 5

5 6

1 3 4 6

Output

2

2 1 2 3

2 4 5 6

Input

4 3 4

1 2

1 3

1 4

1 2 3 4

Output

2

1 1 2

2 3 1 4

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 06:24:50 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|