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

F. Minimal k-covering

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a bipartite graph *G* = (*U*, *V*, *E*), *U* is the set of vertices of the first part, *V* is the set of vertices of the second part and *E* is the set of edges. There might be multiple edges.

Let's call some subset of its edges *k*-covering iff the graph has each of its vertices incident to at least *k* edges. Minimal *k*-covering is such a *k*-covering that the size of the subset is minimal possible.

Your task is to find minimal *k*-covering for each , where *minDegree* is the minimal degree of any vertex in graph *G*.

Input

The first line contains three integers *n*_{1}, *n*_{2} and *m* (1 ≤ *n*_{1}, *n*_{2} ≤ 2000, 0 ≤ *m* ≤ 2000) — the number of vertices in the first part, the number of vertices in the second part and the number of edges, respectively.

The *i*-th of the next *m* lines contain two integers *u*_{i} and *v*_{i} (1 ≤ *u*_{i} ≤ *n*_{1}, 1 ≤ *v*_{i} ≤ *n*_{2}) — the description of the *i*-th edge, *u*_{i} is the index of the vertex in the first part and *v*_{i} is the index of the vertex in the second part.

Output

For each print the subset of edges (minimal *k*-covering) in separate line.

The first integer *cnt*_{k} of the *k*-th line is the number of edges in minimal *k*-covering of the graph. Then *cnt*_{k} integers follow — original indices of the edges which belong to the minimal *k*-covering, these indices should be pairwise distinct. Edges are numbered 1 through *m* in order they are given in the input.

Examples

Input

3 3 7

1 2

2 3

1 3

3 2

3 3

2 1

2 1

Output

0

3 3 7 4

6 1 3 6 7 4 5

Input

1 1 5

1 1

1 1

1 1

1 1

1 1

Output

0

1 5

2 4 5

3 3 4 5

4 2 3 4 5

5 1 2 3 4 5

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 19:04:24 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|