y2018-4-1-D

#include <vector>
#include <memory>
#include <fstream>
#include <algorithm>
#include <set>

#pragma warning(disable : 4018)

#define FILL(A, c) std::generate((A).begin(), (A).end(), []() { return (c); })

typedef unsigned uint;
typedef std::vector<bool> bvec;
typedef std::vector<unsigned> uivec;
typedef std::vector<int> ivec;
typedef std::pair<uint, uint> edge;
typedef std::vector<ivec> matr;

struct guests
{
  size_t amt;
  std::set<int> girls, boys;
};

std::ostream & operator<<(std::ostream & os, const std::set<int> & v)
{
  for (const auto & a : v)
    os << a << " ";

  return os;
}

struct kun
{
  matr G, G1;
private:
  guests my_guests_ = { 0 };
  static uint n_, m_;
  ivec matching_;
  bvec used_, mark_;

public:
  explicit kun(const uint n = 0, const uint m = 0) :
  G(n + m, ivec()), G1(n + m, ivec())
  {
    n_ = n, m_ = m;
  }

  friend std::ostream & operator<<(std::ostream & os, const kun & m_m)
  {
    os << std::endl << m_m.my_guests_.amt << std::endl <<
      m_m.my_guests_.boys.size() << " " << m_m.my_guests_.girls.size() << std::endl <<
      m_m.my_guests_.boys << std::endl << m_m.my_guests_.girls;

    return os;
  }

  void build_g1()
  {
    for (int i = 0; i < n_; i++)
    {
      for (int j = n_; j < n_ + m_; j++)
        if ((std::find(G[i].begin(), G[i].end(), j) == G[i].end())
         && (std::find(G[j].begin(), G[j].end(), i) == G[j].end()))
          G1[i].push_back(j);
    }

    for (int i = n_; i < n_ + m_; i++)
    {
      for (int j = 0; j < n_; j++)
        if ((std::find(G[i].begin(), G[i].end(), j) == G[i].end())
          && (std::find(G[j].begin(), G[j].end(), i) == G[j].end()))
          G1[i].push_back(j);
    }
  }

  kun & obtain_max_matching()
  {
    // 1
    build_g1();

    // 2
    matching_ = ivec(n_ + m_, -1);
    used_.resize(n_ + m_);
    mark_ = bvec(n_ + m_, false);
    for (uint i = 0; i < n_ + m_; ++i)
      FILL(used_, false), dfs(i);

    // 3
    FILL(used_, false);
    for (uint i = 0; i < n_; ++i)
      if (!mark_[i]) dfs1(i);

    // 4
    for (uint i = 0; i < n_; i++)
      if (used_[i])
        my_guests_.girls.insert(i + 1);
    for (uint i = n_; i < n_ + m_; i++)
      if (!used_[i])
        my_guests_.boys.insert(i - n_ + 1);
    my_guests_.amt = my_guests_.boys.size() + my_guests_.girls.size();

    return *this;
  }
private:
  bool dfs(const uint v)
  {
    if (used_[v])
      return false;

    used_[v] = true;

    for (const auto to : G1[v])
      if (matching_[to] == -1 || dfs(matching_[to]))
      {
        matching_[to] = v;
        return mark_[v] = mark_[to] = true;
      }
    return false;
  }

  void dfs1(const uint v)
  {
    if (used_[v])
      return;

    used_[v] = true;

    for (const auto to : G1[v])
    {
      if (v >= n_ && (matching_[to] == v || matching_[v] == to))
        dfs(to);
      else if (v < n_ && (matching_[to] != v && matching_[v] != to))
        dfs(to);
    }
  }
};

uint kun::n_, kun::m_;

int main()
{
  uint k = 0, n = 0, m = 0, a = 0, b = 0, w = 0;
  std::ifstream in("birthday.in");
  std::ofstream out("birthday.out");

  in >> k;

  while (k--)
  {
    in >> m >> n;

    kun calculator(n, m);

    for (uint i = 0; i < m; i++)
    {
    again:
      in >> a;
      if (a == 0)
        continue;
      calculator.G[i + n].emplace_back(a - 1);
      // calculator.G[a - 1].emplace_back(i + n);
      goto again;
    }

    if (m == 0 && n == 0)
      out << 0 << std::endl << 0 << " " << 0 << std::endl << std::endl;
    else
      out << calculator.obtain_max_matching() << std::endl << std::endl;
  }

  in.close(), out.close();

  return 0;
}