Road Construction (Problem L, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 2 sec
Memory limit: 256MB
Author: Jonathan Irvin Gunawan

# Problem Statement

There are $N$ cities in the country of Numbata, numbered from $1$ to $N$. Currently, there is no road connecting them. Therefore, each of these $N$ cities proposes a road candidate to be constructed.

City $i$ likes to connect with city $A_i$, so city $i$ proposes to add a direct bidirectional road connecting city $i$ and city $A_i$. It is guaranteed that no two cities like to connect with each other. In other words, there is no pair of integers $i$ and $j$ where $A_i = j$ and $A_j = i$. It is also guaranteed that any pair of cities are connected by a sequence of road proposals. In other words, if all proposed roads are constructed, then any pair of cities are connected by a sequence of constructed road.

City $i$ also prefers the road to be constructed using a specific material. Each material can be represented by an integer (for example, $0$ for asphalt, $1$ for wood, etc.). The material that can be used for the road connecting city $i$ and city $A_i$ is represented by an array $B_i$ containing $M_i$ integers: $[(B_i)_1, (B_i)_2, \ldots, (B_i)_{M_i}]$. This means that the road connecting city $i$ and city $A_i$ can be constructed with either of the material in $B_i$.

There are $K$ workers to construct the roads. Each worker is only familiar with one material, thus can only construct a road with a specific material. In particular, the $i^{\text{th}}$ worker can only construct a road with material $C_i$. Each worker can only construct at most one road. You want to assign each worker to construct a road such that any pair of cities are connected by a sequence of constructed road.

# Input

Input begins with a line containing two integers: $N$ $K$ $(3 \leq N \leq 2000;\ 1 \leq K \leq 2000)$ representing the number of cities and the number of workers, respectively.  
The next $N$ lines each contains several integers: $A_i\ M_i\ (B_i)_1,\ (B_i)_2,\ \cdots,\ (B_i)_{M_i}$ $(1 \leq A_i \leq N;\ A_i \neq i;\ 1 \leq M_i \leq 10000;\ 0 \leq (B_i)_1 < (B_i)_2 < \cdots < (B_i)_{M_i} \leq 10^9)$ representing the bidirectional road that city $i$ likes to construct.  
It is guaranteed that the sum of $M_i$ does not exceed $10000$.  
It is also guaranteed that no two cities like to connect with each other and any pair of cities are connected by a sequence of road proposals.  
The next line contains $K$ integers: $C_i$ $(0 \leq C_i \leq 10^9)$ representing the material that is familiarized by the workers.

# Output

If it is not possible to assign each worker to construct a road such that any pair of cities are connected by a sequence of constructed road, simply output `-1` in a line.  
Otherwise, for each worker, output in the same order as input, output in a line two integers (separated by a single space): $u$ and $v$ in any order.  
This means that the $i^{\text{th}}$ worker constructs a direct bidirectional road connecting city $u$ and $v$.  
If the worker does not construct any road, output `0 0` (without quotes) instead.  
Each pair of cities can only be assigned to at most one worker.  
You may output any assignment as long as any pair of cities are connected by a sequence of constructed road.

# Sample Input #1
```
4 5
2 2 1 2
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5
```
# Sample Output #1
```
1 2
2 3
3 4
0 0
4 2
```
# Explanation for the sample input/output #1

We can assign the workers to construct the following roads:

- The first worker constructs a road connecting city 1 and city 2.
- The second worker constructs a road connecting city 2 and city 3.
- The third worker constructs a road connecting city 3 and city 4.
- The fourth worker does not construct any road.
- The fifth worker constructs a road connecting city 4 and city 2.

Therefore, any pair of cities are now connected by a sequence of constructed road.

# Sample Input #2
```
4 5
2 2 10 20
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5
```
# Sample Output #2
```
-1
```
# Explanation for the sample input/output #2

There is no worker that can construct a road connecting city 1, thus city 1 is certainly isolated.


Sample inputs:
4 5
2 2 1 2
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5

4 5
2 2 10 20
3 2 2 3
4 2 3 4
2 2 4 5
1 2 3 4 5

Sample outputs:
1 2
2 3
3 4
0 0
4 2

-1

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

Let us consider the easier version of this problem first if there are only $N - 1$ (instead of $N$) road proposals. In this case, all roads have to be constructed. Therefore, we need to find a surjective mapping from the set of road proposals to the set of workers.

We can do this by modeling a bipartite graph where we created a node for each road proposal and worker. We add an edge connecting a road proposal node and a worker node if the worker can construct the road proposal. The maximum cardinality bipartite matching should give us a surjective matching from the set of road proposals to the set of workers if it exists. We will have $O(NK)$ edges with this approach.

We can reduce the number of edges by creating a node for each material (that exists in the input) instead of for each worker. Each of these nodes has a capacity (the number of times this node can be matched) equals to the number of workers that is familiar with the material. We add an edge connecting a road proposal node and a material node if the road proposal can be constructed with the material. Since a node $u$ will be connected to $M_u$ nodes, we will have $O(\sum_{i=1}^{N} M_i)$ edges with this approach.

Now let’s get back to the original problem where we have $N$ edges. Therefore, the road proposals will contain exactly one cycle. Let’s denote $A$ as the set of road proposals inside the cycle and $B$ as the set of road proposals outside the cycle. We need to construct at least $|A| - 1$ roads in set $A$ and all roads in set $B$.

There are two ways to do this. Since we want to avoid redundant worker assignment, we want to keep at most $|A| - 1$ workers to construct the set of road proposals in $A$. Therefore, we can create an additional node (with a capacity of $|A| - 1$) that is connected to the maximum flow source and the set of road proposal nodes in $A$. Alternatively, the easier method is to run the maximum cardinality bipartite matching on set $B$ first, before running it on set $A$. We will still have $O(\sum_{i=1}^{N} M_i)$ edges with this approach.

Special judge (C++ scorer):
#include <bits/stdc++.h>
using namespace std;

int ac() {
  puts("AC");
  return 0;
}

int wa(string message) {
  fprintf(stderr, "%s\n", message.c_str());
  puts("WA");
  return 0;
}

const int IMPOSSIBLE_KEY = -1;

int main(int argc, char *argv[])
{
  FILE *in = fopen(argv[1], "r");
  FILE *out = fopen(argv[2], "r");  // Judge's
  FILE *con = fopen(argv[3], "r");

  int N, K;
  fscanf(in, "%d %d", &N, &K);

  vector<unordered_map<int, unordered_set<int>>> materials(N);

  for (int i = 0; i < N; ++i) {
    int A, M;
    fscanf(in, "%d %d", &A, &M);
    --A;
    while (M--) {
      int B;
      fscanf(in, "%d", &B);
      materials[i][A].insert(B);
      materials[A][i].insert(B);
    }
  }

  vector<int> C(K);
  for (int i = 0; i < K; ++i) {
    fscanf(in, "%d", &C[i]);
  }

  int judge;
  fscanf(out, "%d", &judge);

  if (fscanf(out, "%d", &judge) == EOF) {
    int contestant;
    if (fscanf(con, "%d", &contestant) != 1) {
      return wa("Unexpected EOF.");
    }
    if (contestant != IMPOSSIBLE_KEY) {
      return wa("Judge answer is `impossible`, contestant answer is not.");
    }
  } else {
    vector<int> parent(N);
    for (int i = 0; i < N; ++i) {
      parent[i] = i;
    }

    function<int (int)> findRoot = [&](int U) {
      return parent[U] = (U == parent[U] ? U : findRoot(parent[U]));
    };

    vector<unordered_set<int>> edges(N);

    for (int i = 0; i < K; ++i) {
      int U, V;
      if (fscanf(con, "%d %d", &U, &V) != 2) {
        return wa("Unexpected EOF.");
      }
      if (U == 0 && V == 0) {
        continue;
      }
      if (U < 1 || U > N || V < 1 || V > N) {
        return wa("Index out of bound.");
      }
      --U;
      --V;
      if (edges[U].count(V)) {
        return wa("A pair of cities is directly connected by >1 road.");
      }
      edges[U].insert(V);
      edges[V].insert(U);
      if (!materials[U][V].count(C[i])) {
        return wa("Worker is not familiar with the assigned road material.");
      }

      parent[findRoot(U)] = findRoot(V);
    }
    for (int i = 0; i < N; ++i) {
      if (findRoot(i) != findRoot(0)) {
        return wa("Graph is not connected.");
      }
    }
  }

  fscanf(con, "\n");
  char dummy;
  if (fscanf(con, "%c", &dummy) == 1) {
    return wa("Expected EOF.");
  }

  return ac();
}