#include <cstddef>
#include <set>
#include <vector>
#include <fstream>
#include <iostream>
#include <sstream>

// _______________________________________________________________________________

/// \brief  Finds the maximum size matching of the bipartite graph
///         Uses the Hopcroft-Karp algorithm.
/// 
/// http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
class HopcroftKarp
{ private:
  
  ::std::size_t                                           const m_n0;
  ::std::size_t                                           const m_n2;
  ::std::vector< ::std::vector< ::std::size_t >  > const      & m_adj2;
  ::std::size_t                                                 m_nil;
  ::std::size_t                                                 m_inf;
  ::std::vector< ::std::size_t >                                m_pair0;
  ::std::vector< ::std::size_t >                                m_pair2;
  ::std::vector< ::std::size_t >                                m_dist;
  ::std::vector< ::std::size_t >                                m_queue;
  ::std::vector< ::std::size_t >                              & m_visited;
  ::std::size_t                                                 m_maxSize;
  public:
  
  HopcroftKarp
  ( ::std::size_t                                           const n0
  , ::std::size_t                                           const n2
  , ::std::vector< ::std::vector < ::std::size_t > > const      & adj2
  )
  ;
  
  private:
  
  void
  acquireSpace
  ()
  ;
  
  void
  solve
  ()
  noexcept
  ;
  
  bool
  bfs
  ()
  noexcept
  ;
  
  bool
  dfs
  ( ::std::size_t  const v0
  )
  noexcept
  ;
  
  public:
  
  ::std::size_t
  getMaxSize
  ()
  const
  noexcept
  ;
  
  ::std::vector< ::std::size_t> const  &
  getPair0
  ()
  const
  noexcept
  ;
  
} // class HopcroftKarp
;

HopcroftKarp::
HopcroftKarp
( ::std::size_t                                           const n0
, ::std::size_t                                           const n2
, ::std::vector< ::std::vector < ::std::size_t > > const      & adj2
)
: m_n0(n0)
, m_n2(n2)
, m_adj2(adj2)
, m_visited(m_queue)
{ // Let use make a note on the 'm_visited(m_queue)' above.
  // The m_queue vector is used by the BFS.    The DFS is performed after the BFS.
  // The DFS reuses the m_queue vector.    To keep the code readable, we make a
  // reference.
  acquireSpace();
  // no-throw, no-fail
  solve();
}

void
HopcroftKarp::
acquireSpace
()
{ ::std::vector< ::std::size_t>  tmpPair0(m_n0);
  ::std::vector< ::std::size_t>  tmpPair2(m_n2);
  ::std::vector< ::std::size_t>  tmpDistance(m_n0);
  ::std::vector< ::std::size_t>  tmpQueue(m_n0);
  ::std::size_t  const maxn02 =
    ((m_n0 > m_n2) ? m_n0 : m_n2);
  // no-throw, no-fail
  m_nil = maxn02;
  m_inf = m_n0;   // ∞ only needs to be an upper bound for values
                  //   in the queue ( m_queue ).
  m_pair0.swap(tmpPair0);
  m_pair2.swap(tmpPair2);
  m_dist.swap(tmpDistance);
  m_queue.swap(tmpQueue);
}

void
HopcroftKarp::
solve
()
noexcept
{ // Start with the empty matching.
  ::std::size_t  v0;
  for(v0 = 0; m_n0 > v0; ++v0)
  { m_pair0[v0] = m_nil; }
  ::std::size_t  v2;
  for(v2 = 0; m_n2 > v2; ++v2)
  { m_pair2[v2] = m_nil; }
  // Improve matching.
  m_maxSize = 0;
  bool  existsAugmentingPath =
    bfs();
  while(existsAugmentingPath)
  { // Augment.
    for(v0 = 0; m_n0 > v0; ++v0)
    { m_visited.at(v0) = 0; }
    for(v0 = 0; m_n0 > v0; ++v0)
    { if(m_nil == (m_pair0.at(v0) )  )
      { if(true == (dfs(v0) )  )
        { ++m_maxSize;
        }
      }
    }
    // Search for augmenting paths.
    existsAugmentingPath = bfs();
  }
  // Now, processing is complete.
}

bool
HopcroftKarp::
bfs
()
noexcept
{ ::std::size_t  qOut = 0; // Queue out.
  ::std::size_t  qIn  = 0; // Queue in.
  ::std::size_t  v0;       // Vertex from partition zero.
  for(v0 = 0; m_n0 > v0; ++v0)
  { if(m_nil == (m_pair0.at(v0) )  )
    { m_queue.at(qIn) = v0;
      ++qIn;
      m_dist.at(v0) = 0;
    }
    else
    { m_dist.at(v0) = m_inf; }
  }
  ::std::size_t  distOfNil = m_inf; // 'dist[nil] = ∞'
  ::std::size_t  distOfV0;
  
  while(qOut < qIn)
  { v0 = m_queue.at(qOut);
    ++qOut;
    distOfV0 = m_dist.at(v0);
    if(distOfNil > distOfV0)
    { ::std::vector< ::std::size_t > const  & adj = m_adj2.at(v0);
      for( ::std::size_t  const v2 : adj )
      { ::std::size_t  const x0 = m_pair2.at(v2);
        if(m_nil != x0)
        { if(m_inf == (m_dist.at(x0) )  )
          { m_dist.at(x0) = (1 + distOfV0);
            m_queue.at(qIn) = x0;
            ++qIn;
          }
        }
        else
        { if(m_inf == distOfNil)
          { distOfNil = (1 + distOfV0);
          }
        }
      }
    }
  }
  
  bool  const existsAugmentingPath =
    (m_inf != distOfNil);
  return existsAugmentingPath;
}

bool
HopcroftKarp::
dfs
( ::std::size_t  const v0
)
noexcept
{ m_visited.at(v0) = 1;
  ::std::vector< ::std::size_t > const  & adj =
    m_adj2.at(v0);
  for( ::std::size_t  const v2 : adj )
  { ::std::size_t  const x0 = m_pair2.at(v2);
    if(m_nil != x0)
    { if(0 == (m_visited.at(x0) )  )
      { if( (1 + (m_dist.at(v0) )  )  == (m_dist.at(x0) )  )
        { if(true == dfs(x0) )
          { m_pair0[v0] = v2;
            m_pair2[v2] = v0;
            return true; // Augmenting path.
          }
        }
      }
    }
    else
    { m_pair0[v0] = v2;
      m_pair2[v2] = v0;
      return true; // Augmenting path.
    }
  }
  return false; // No augmenting path.
}

::std::size_t
HopcroftKarp::
getMaxSize
()
const
noexcept
{ return m_maxSize;
}

::std::vector< ::std::size_t> const  &
HopcroftKarp::
getPair0
()
const
noexcept
{ return m_pair0;
}

// _______________________________________________________________________________

void
logErrorMessage
( char const  * pErrorMessage
)
{ if(nullptr == pErrorMessage)
  { pErrorMessage = "Error in error message.";
  }
  ::std::cerr << pErrorMessage << ::std::endl;
}

// _______________________________________________________________________________

::std::size_t  const maxn0 = 10000;
::std::size_t  const maxn2 = 10000;
::std::size_t  const max_e = 100000;

/// \brief  Reads question.
///         Question is input.
class QuestionReader
{ private:
  
  ::std::size_t                                          & m_n0;
  ::std::size_t                                          & m_n2;
  ::std::vector< ::std::vector < ::std::size_t >  >      & m_adj2;
  
  bool                                               const m_ok;
  
  public:
  
  QuestionReader
  ( bool                                                & ok
  , ::std::size_t                                       & n0
  , ::std::size_t                                       & n2
  , ::std::vector < ::std::vector < ::std::size_t >  >  & adj2
  )
  ;
  
  private:
  
  bool
  readBipartiteGraph
  ()
  ;
  
} // class QuestionReader
;

QuestionReader::
QuestionReader
( bool                                                & ok
, ::std::size_t                                       & n0
, ::std::size_t                                       & n2
, ::std::vector < ::std::vector < ::std::size_t >  >  & adj2
)
: m_n0(n0)
, m_n2(n2)
, m_adj2(adj2)
, m_ok(readBipartiteGraph() )
{ ok = m_ok;
}

bool
QuestionReader::
readBipartiteGraph
()
{ ::std::size_t  n0;
  ::std::size_t  n2;
  ::std::size_t  m;  // size_t is unsigned
  ::std::ifstream  is("cuplaj.in");
  is >> n0 >> n2 >> m;
  bool  ok;
  ok = (    ((1 <= n0) && (maxn0 >= n0))
         && ((1 <= n2) && (maxn2 >= n2))
         && (             (max_e >=  m))
       )
       ;
  if( !ok)
  { logErrorMessage("bad input: n0, n2,  m.");
    return false; // Failure.
  }
  // Read edges.
  ::std::vector
    < ::std::vector< ::std::size_t >  >
    adj2(n0);
  ::std::size_t  t;
  ::std::size_t  x;
  ::std::size_t  y;
  for(t=0; m>t; ++t)
  { is >> x >> y;
    ok = (     ((1 <= x) && (n0 >= x))
           &&  ((1 <= y) && (n2 >= y))
         )
         ;
    if( !ok)
    { logErrorMessage("bad input: bad edge");
      return false; // Failure.
    }
    --x; --y;
    ::std::vector< ::std::size_t >  & adj =
      adj2.at(x);
    adj.push_back(y);
  }
  
  ok = (! (is.fail() )  );
  if( !ok)
  { logErrorMessage("Bad input: input stream");
    return false; // Failure.
  }
  
  // no-throw, no-fail
  m_n0 = n0;
  m_n2 = n2;
  m_adj2.swap(adj2);
  return true; // Success.
}


// _______________________________________________________________________________

/// \brief  http://www.infoarena.ro/problema/cuplaj
class Cuplaj
{ private:
  
  ::std::size_t                                           m_n0;
  ::std::size_t                                           m_n2;
  ::std::vector< ::std::vector< ::std::size_t >  >        m_adj2;
  ::std::size_t                                           m_ans0;
  ::std::vector< ::std::size_t >                          m_ans2;
  bool                                              const m_ok;
  
  public:
  
  Cuplaj
  ( bool  & ok
  )
  ;
  
  private:
  
  bool
  solve
  ()
  ;
  
  bool
  readQuestion
  ()
  ;
  
  bool
  computeAnswer
  ()
  ;
  
  bool
  writeAnswer
  ()
  ;
  
} // class Senat
;

Cuplaj::
Cuplaj
( bool  & ok
)
: m_ok(solve() )
{ ok = m_ok;
}

bool
Cuplaj::
solve
()
{ bool  ok;
  
  ok = readQuestion();
  if( !ok)
  { return false; } // Failure.    The called logged.
  
  ok = computeAnswer();
  if( !ok)
  { return false; } // Failure.    The called logged.
  
  ok = writeAnswer();
  if( !ok)
  { return false; } // Failure.    The called logged.
  
  return true; // Success.
}

bool
Cuplaj::
readQuestion
()
{ bool  ok;
  
  QuestionReader  reader(ok, m_n0, m_n2, m_adj2);
  if( !ok)
  { return false; } // Failure.    The called logged.
  
  return true; // Success.
}

bool
Cuplaj::
computeAnswer
()
{ HopcroftKarp  theAlgorithm(m_n0, m_n2, m_adj2);
  ::std::size_t  const maxSize = theAlgorithm.getMaxSize();
  ::std::vector< ::std::size_t > const  & pair0 =
    theAlgorithm.getPair0();
  ::std::vector< ::std::size_t >  tmp(pair0);
  // no-throw, no-fail
  m_ans0 = maxSize;
  m_ans2.swap(tmp);
  return true; // Success.
}

bool
Cuplaj::
writeAnswer
()
{ ::std::ofstream        os("cuplaj.out");
  os << m_ans0 << ::std::endl;
  ::std::size_t  i;
  ::std::size_t  x;
  ::std::size_t  y;
  for(i=0; m_n0 > i; ++i)
  { y = m_ans2.at(i);
    if(m_n2 > y)
    { x = i; ++x; ++y;
      os << x << ' ' << y << ::std::endl;
    }
  }
  os.close();
  
  bool  const ok =
    os.good();
  if( !ok)
  { logErrorMessage("output error.");
    return false; // Failure.
  }
  
  return true; // Success.
}

// _______________________________________________________________________________

bool
solveCuplaj
()
{ bool  ok;
  
  Cuplaj  problem(ok);
  if( !ok)
  { return false; } // Failure.    The called logged.
  
  return true; // Success.
}

// _______________________________________________________________________________

int
main()
{ int  status;
  try
  { bool  const ok = solveCuplaj();
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2;
  }
  return status;
}