#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
std::vector<std::pair<int, int>> bipartite_matching(int n, const std::vector<std::pair<int, int>>& edg) {
std::vector<int> vec(n, -1);
std::vector<int> cnt(n + 1);
std::vector<int> gr(edg.size() * 2);
{
for (auto [u, v] : edg) {
cnt[u]++, cnt[v]++;
}
for (int i = 0, c = 0; i <= n; i++) {
c += cnt[i], cnt[i] = c;
}
for (int i = 0; i < edg.size(); i++) {
auto& [u, v] = edg.rbegin()[i];
gr[--cnt[u]] = v;
gr[--cnt[v]] = u;
}
}
struct Data {
int used, prev, root, depth;
};
std::vector<Data> data(n, Data{0, 0, 0, 0});
int used_mark = 0;
std::vector<int> deque(n);
int deque_beg_ptr = 0, deque_end_ptr = 0;
int prev_min_len = 0;
while (true) {
clock_t beg = clock();
int cur_min_len = n;
used_mark++;
deque_beg_ptr = deque_end_ptr = 0;
for (int i = 0; i < n; i++) {
if (vec[i] == -1) {
data[i] = {used_mark, -1, i, 0};
deque[deque_end_ptr++] = i;
}
}
int aug_cnt = 0;
while (deque_beg_ptr < deque_end_ptr) {
int v = deque[deque_beg_ptr++];
if (vec[data[v].root] != -1) {
continue;
}
bool aug_found = false;
for (int ti = cnt[v]; ti < cnt[v + 1]; ti++) {
int t = gr[ti];
if (data[t].used == used_mark && data[t].depth == 0 && vec[data[t].root] == -1) {
aug_cnt++;
vec[v] = t, vec[t] = v;
int len = 1;
for (int x : std::array<int, 2>{v, t}) {
for (; data[x].prev != -1; x = data[x].prev) {
if (data[x].depth == 1) {
vec[x] = data[x].prev, vec[data[x].prev] = x;
}
len++;
}
}
cur_min_len = std::min(cur_min_len, len);
aug_found = true;
break;
}
}
if (aug_found) {
continue;
}
for (int ti = cnt[v]; ti < cnt[v + 1]; ti++) {
int t = gr[ti];
if (data[t].used != used_mark) {
int t2 = vec[t];
data[t] = {used_mark, v, data[v].root, 1};
data[t2] = {used_mark, t, data[v].root, 0};
deque[deque_end_ptr++] = t2;
}
}
}
if (!aug_cnt) {
break;
}
std::cerr << aug_cnt << " " << cur_min_len << " ";
std::cerr << (clock() - beg) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms ";
if (prev_min_len >= cur_min_len) {
std::cerr << " FUCK!!!";
}
std::cerr << "\n";
prev_min_len = cur_min_len;
}
std::vector<std::pair<int, int>> res;
for (int i = 0; i < n; i++) {
if (vec[i] > i) {
res.push_back({i, vec[i]});
}
}
return res;
}
using std::cin, std::cout;
// io from https://judge.yosupo.jp/submission/154408
namespace IO {
constexpr bool UNSAFE = false;
constexpr int GLOB_BUF_SIZE = 1 << 15;
#ifndef DEBUG
#define CHANGE_DEFAULT_STREAMS
static struct FastInput {
FastInput() {
if constexpr (UNSAFE) {
chars_read = fread(buf, 1, BUF_SIZE, in);
buf_pos = 0;
buf[0] = (chars_read == 0 ? -1 : buf[0]);
}
}
static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
char buf[BUF_SIZE];
size_t chars_read = 0;
size_t buf_pos = 0;
FILE* in = stdin;
char cur = 0;
inline char get_char() {
if constexpr (!UNSAFE) {
if (buf_pos >= chars_read) {
chars_read = fread(buf, 1, BUF_SIZE, in);
buf_pos = 0;
buf[0] = (chars_read == 0 ? -1 : buf[0]);
}
}
return cur = buf[buf_pos++];
}
template <typename T>
inline FastInput* tie(T) {
return this;
}
inline void sync_with_stdio(bool) {}
inline explicit operator bool() { return cur != -1; }
inline static bool is_blank(char c) { return c <= ' '; }
inline bool skip_blanks() {
while (is_blank(cur) && cur != -1) get_char();
return cur != -1;
}
inline FastInput& operator>>(char& c) {
skip_blanks();
c = cur;
return *this;
}
inline FastInput& operator>>(std::string& s) {
if (skip_blanks()) {
s.clear();
do {
s += cur;
} while (!is_blank(get_char()));
}
return *this;
}
template <typename T>
inline FastInput& read_integer(T& n) {
// unsafe, doesn't check that characters are actually digits
n = 0;
if (skip_blanks()) {
int sign = +1;
if (cur == '-') {
sign = -1;
get_char();
}
do {
n += n + (n << 3) + cur - '0';
} while (!is_blank(get_char()));
n *= sign;
}
return *this;
}
template <typename T>
inline typename std::enable_if<std::is_integral<T>::value, FastInput&>::type
operator>>(T& n) {
return read_integer(n);
}
#if !defined(_WIN32) || defined(_WIN64)
inline FastInput& operator>>(__int128& n) { return read_integer(n); }
#endif
template <typename T>
inline typename std::enable_if<std::is_floating_point<T>::value,
FastInput&>::type
operator>>(T& n) {
// not sure if really fast, for compatibility only
n = 0;
if (skip_blanks()) {
std::string s;
(*this) >> s;
sscanf(s.c_str(), "%lf", &n);
}
return *this;
}
} fast_input;
#define cin IO::fast_input
static struct FastOutput {
static constexpr int BUF_SIZE = GLOB_BUF_SIZE;
char buf[BUF_SIZE];
size_t buf_pos = 0;
static constexpr int TMP_SIZE = GLOB_BUF_SIZE;
char tmp[TMP_SIZE];
FILE* out = stdout;
inline void put_char(char c) {
buf[buf_pos++] = c;
if (buf_pos == BUF_SIZE) {
fwrite(buf, 1, buf_pos, out);
buf_pos = 0;
}
}
~FastOutput() { fwrite(buf, 1, buf_pos, out); }
inline FastOutput& operator<<(char c) {
put_char(c);
return *this;
}
inline FastOutput& operator<<(const char* s) {
while (*s) put_char(*s++);
return *this;
}
inline FastOutput& operator<<(const std::string& s) {
for (auto x : s) put_char(x);
return *this;
}
template <typename T>
inline char* integer_to_string(T n) {
// beware of TMP_SIZE
char* p = tmp + TMP_SIZE - 1;
if (n == 0)
*--p = '0';
else {
bool is_negative = false;
if (n < 0) {
is_negative = true;
n = -n;
}
while (n > 0) {
*--p = (char)('0' + n % 10);
n /= 10;
}
if (is_negative) *--p = '-';
}
return p;
}
template <typename T>
inline typename std::enable_if<std::is_integral<T>::value, char*>::type
stringify(T n) {
return integer_to_string(n);
}
#if !defined(_WIN32) || defined(_WIN64)
inline char* stringify(__int128 n) { return integer_to_string(n); }
#endif
template <typename T>
inline typename std::enable_if<std::is_floating_point<T>::value, char*>::type
stringify(T n) {
sprintf(tmp, "%.17f", n);
return tmp;
}
template <typename T>
inline FastOutput& operator<<(const T& n) {
auto p = stringify(n);
for (; *p != 0; p++) put_char(*p);
return *this;
}
} fast_output;
#define cout IO::fast_output
#endif
} // namespace IO
int32_t main() {
std::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n1, n2, m;
cin >> n1 >> n2 >> m;
std::vector<std::pair<int, int>> edg(m);
for (auto& [u, v] : edg) {
cin >> u >> v;
v += n1;
}
std::mt19937 rnd(2086);
std::shuffle(edg.begin(), edg.end(), rnd);
clock_t beg = clock();
auto ans = bipartite_matching(n1 + n2, edg);
cout << (int)ans.size() << '\n';
for (auto [u, v] : ans) {
cout << u << ' ' << v - n1 << '\n';
}
return 0;
}