시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 29 4 4 13.793%

## 문제

Can you replicate my bachelor thesis in 5 hours?

I give you an undirected bipartite graph. Let K be the size of its maximum cardinality matching. Devise an algorithm to find a matching of size at least 0.95 · K.

If you want to get Accepted, I suggest you to optimize your code as good as you can.

## 입력

The first line contains three positive integers n1, n2 and m (1 ≤ n1, n2, m ≤ 2 · 106) — the number of vertices in the first part, the number of vertices in the second part and the number of edges in the graph, respectively.

The next m lines describe edges, one per line. Description of each edge is two integers u and v (1 ≤ u ≤ n1, 1 ≤ v ≤ n2) — the ids of vertices in first and second parts that are connected by the edge. There is no pair of edges connecting the same vertices.

## 출력

In the first line print one integer L — the size of the matching you found. The inequality 0.95 · K ≤ L should hold.

In the next L lines print the ids of the edges in your matching. Edges are numbered from 1 to m in the order they are given in input.

## 예제 입력 1

3 2 4
1 1
2 1
3 1
3 2


## 예제 출력 1

2
1
4


## 예제 입력 2

20 20 20
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20


## 예제 출력 2

19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19