A bipartite graph is defined as a graph whose vertex set $V$ can be partitioned into $S$ and $T$, satisfying the following conditions:

1. $S∪T=V$，$S∩T=\varnothing$
2. For all $(x,y)∈E$, either $x∈S$, $y∈T$ or $x∈T$, $y∈S$

A $k$-division scheme of a bipartite graph is defined as a way to color each edge in the graph with any color from $1$ to $k$.

In a given $k$-division scheme of a bipartite graph, let $w_{ij}$ denote the number of edges of color $j$ passing through vertex $i$.

Define the imbalance of node $i$ in a $k$-division scheme as $\max_{w_{ij}} - \min_{w_{ij}}, j ∈ [1, k]$.

The imbalance of a $k$-division scheme is defined as the sum of imbalances over all vertices.

You are given a bipartite graph where each of $S$ and $T$ contains $n$ nodes.

The nodes are numbered from $1$ to $n$.

Initially, the bipartite graph contains no edges, i.e., $V = \varnothing$.

You need to dynamically support adding and removing edges in the graph.

At the same time, you must compute any $k$-division scheme that minimizes the imbalance.

Note that in this problem, the sets $S$ and $T$ will not change as the graph evolves. That is, $S$ and $T$ remain fixed within the same problem (test case).

Task

You need to implement two functions: Init and Modify.

• Init(n, k, Q)

  • n, k are as defined in the problem description.
  • Q is the number of operations.
  • You do not need to return any value.

In each test case, the interaction library will call Init exactly once.

• Modify(x, y)

  • x, y are integers from $1$ to $n$.
  • This function toggles the existence of the edge connecting the $x$-th node in set $S$ to the $y$-th node in set $T$.
  • You need to return any $k$-division scheme after the change.

In each test case, the interaction library will call Modify exactly $Q$ times.

Implementation Details

Only C++ is supported for this problem.

Your source code must include the header file graph.h.

You must implement the following function interfaces:

void Init(int n, int k, int Q);
Division Modify(int x, int y);

The Division type is defined as follows:

struct Division { int color[22][22]; };

Here, $color_{ij}$ represents the color of the edge from the $i$-th node in $S$ to the $j$-th node in $T$.

If the edge does not exist, then this element must be set to 0.

How to Test Your Program

You need to compile the executable in this problem directory using the following command:

g++ -o graph grader.cpp graph.cpp -O2

The executable will read the following data format from standard input:

The first line contains a positive integer $seed$, where $0 \leq seed \leq 2^{30}-1$.

• For debugging convenience, when $seed = 0$, the data will not be encrypted.

The second line contains three integers: $n, k, Q$, satisfying $2 \leq k \leq n \leq 20$, $1 \leq Q \leq 500000$.

After reading input, the interaction library will call the Init function.

Then $Q$ lines follow, each with two integers $x, y$, where $1 \leq x, y \leq n$.

After reading each line, the interaction library will call the Modify function.

The interaction library will output the following information to standard output:

After each call to the Modify function, it will output a line in the form Count: cnt, where cnt is the imbalance of your returned scheme.

• If the scheme you return is invalid, cnt will be -1.

Note: The grader used for final evaluation may differ from the one provided.

Sample Solution

In the problem directory, a sample C++ source code file graph.cpp is provided. You can compile it using the method mentioned above to obtain an executable.

The sample code is only intended to help you understand the problem. Its result is definitely incorrect.

Constraints

For all test data, it is guaranteed that $2 \leq n, k$, $1 \leq Q$

The time and memory limits specified in the problem are shared between your code and the interaction library. We guarantee that for any valid input and any version of the interaction library (including both the released and final judge versions), the total runtime on the OJ will not exceed 0.5s and memory usage will not exceed 12MB. This means the actual available runtime for contestants is at least 0.5s, and the actual available memory is at least 500MB.