P6113 [Template] Maximum Matching in a General Graph.

This is a template problem, with no background.

Given an undirected graph with $n$ vertices and $m$ edges, find the maximum matching of this graph.

The first line contains two positive integers $n$ and $m$, representing the number of vertices and the number of edges in the graph. The next $m$ lines each contain two positive integers $u$ and $v$, indicating that there is an undirected edge connecting $u$ and $v$.

The first line contains one integer, the size of the maximum matching. The second line contains $n$ integers. The $i$-th integer denotes the index of the vertex matched with vertex $i$. If vertex $i$ is unmatched, output $0$. If there are multiple solutions, output any one.

For $50\%$ of the testdata, $n \le 500$. For $100\%$ of the testdata, $2 \le n \le 10^3$ and $1 \le m \le 5 \times 10^4$. This problem has 5 extra test cases. #### Hint To make it easier for you to debug your program, the problem setter provides a ~~very ugly~~ testdata generator [here](https://www.luogu.com.cn/paste/vf7dlo6r). Translated by ChatGPT 5