Description

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

Input Format

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$.

Output Format

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.

10 10
4 3
3 1
4 7
2 10
2 9
3 10
5 9
4 6
1 10
1 7

4
7 9 10 6 0 4 1 0 2 3 

Hint

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.

Translated by ChatGPT 5