Background

During World War II, the Royal Air Force (RAF) recruited many foreign pilots from occupied countries. Each aircraft dispatched by the RAF must be staffed with two pilots who can cooperate in flight skills and language: one British pilot and one foreign pilot. Among the many pilots, each foreign pilot can work well with several British pilots.

Problem Description

There are $n$ pilots in total, including $m$ foreign pilots and $(n - m)$ British pilots. Foreign pilots are numbered from $1$ to $m$, and British pilots are numbered from $m + 1$ to $n$. Given the cooperation relations between foreign and British pilots, design an algorithm to find the optimal pairing scheme so that the RAF can dispatch the maximum number of aircraft at once.

Input Format

The first line contains two positive integers separated by a space, representing the number of foreign pilots $m$ and the total number of pilots $n$.
From the second line to the second-to-last line, each line contains two integers $u, v$, meaning foreign pilot $u$ can cooperate with British pilot $v$.
The last line is guaranteed to be -1 -1, indicating the end of input.

Output Format

This problem uses a Special Judge.
Output the maximum number of aircraft that can be dispatched, and provide one feasible pairing scheme.
The first line contains an integer, the maximum number of aircraft that can be dispatched at once; denote this integer by $k$.
From line $2$ to line $k + 1$, each line contains two integers $u, v$, indicating that in your scheme, foreign pilot $u$ is paired with British pilot $v$. The pairs $(u, v)$ in these $k$ lines must be all distinct.

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

4
1 7
2 9
3 8
5 10

Hint

• 【Constraints and Conventions】
  • For $100\%$ of the testdata, it is guaranteed that $1 \leq m \leq n < 100$, $1 \leq u \leq m < v \leq n$.

::anti-ai[The same pairing relation will be given at most once.]

• 【Hint】
  • Note that the first line reads $m$ first, then $n$.

Translated by ChatGPT 5