这是一道交互题

定义二分图为一种可以将点集$V$划分为$S$和$T$的图，满足条件：

1. $S∪T=V$，$S∩T= \varnothing$
2. 对于所有 $(x,y)∈E$，有 $x∈S$, $y∈T$ 或x∈T$, $y∈S$

定义二分图的一个$k$划分方案为将二分图中每一条边染任意一种$1$到$k$之间的颜色的方案。

定义在二分图的一种$k$划分方案中$w_{ij}$表示经过第$i$个点的颜色为$j$的边的条数。

定义在二分图的一种$k$划分方案中节点$i$的不平均度为$\max_{w_{ij}}-\min_{w_{ij}}$, $j∈[1,k]$。

定义二分图的一种$k$划分方案中的不平均度为所有节点的不平均度之和。

题目描述

给定一个$S$,$T$中各有$n$个点的二分图。

其中点的编号为$1, \dots ,n$。

初始时候二分图内没有任何一条边,也就是$V=\varnothing$。

你需要动态支持向图中加边，删边。

同时求出任意一个不均匀度最小的$k$划分方案。

注意，在本题中$S$集合和$T$集合中的点不会随着图改变，也就是说,$S$集合和$T$集合在同一个问题(测试点)中是不变的。

任务介绍

你需要实现两个函数Init和Modify。

• Init(n,k,Q)

  • n,k含义见题目描述。
  • Q为操作的个数。
  • 你不需要返回任何值。

在每个测试点中，交互库都会调用恰好一次Init函数。

• Modify(x,y)

  • x,y是两个$1, \dots ,n$的数。
  • 该函数改变连接$S$集合中第$x$个点到$T$集合中第$y$个点的边的存在性。
  • 你需要返回在改变存在性之后的任意一种$k$划分方案。

在每个测试点中，交互库都会调用恰好$Q$次Modify函数。

实现方法

本题只支持C++。

源代码中需要包含头文件graph.h。

你需要实现的函数的相关接口:

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

其中division定义如下

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

其中$color_{ij}$表示$S$集合中的第$i$个节点到$T$集合中的第$j$个节点的边的颜色。

对于不存在那一条边，则该元素值必须为0.

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序：

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

可执行文件将从标准输入读取以下格式的数据：

第一行包含一个正整数$seed$，需要保证$0 \leq seed \leq 2^{30}-1$。 * 为方便选手调试，在$seed$为零时数据不会进行加密。

第二行一共三个正整数，$n,k,Q$，需要保证$2 \leq k \leq n \leq 20 ,1 \leq Q \leq 500000$。

读入完成之后，交互库将会调用Init函数。

接下来$Q$行，一行两个整数$x,y$。需要保证$1 \leq x,y \leq n$

每一行读入完成之后，交互库会调用Modify函数

交互库将会在标准输出中输出以下信息：

每一次调用完Modify函数后，交互库都会输出一行形如Count: cnt的输出，其中cnt为你的方案的不平均度。 * 如果你给出的方案不合法的话cnt会等于 -1。

注意最终测评时使用的 grader 和下发的 grader 不同

样例源代码

在本题目录下，有C++语言的样例源代码graph.cpp。按照上文中提到的方式进行编译，即能通过编译得到可执行程序。

样例源代码只是帮助理解题目，结果一定不正确。

限制与约定

对于所有数据，满足$2 \leq n,k,1 \leq Q$

题目中所给的时间、空间限制为你的代码和交互库加起来可以使用的时间和空间。我们保证，对于任何合法的数据，任何版本的交互库（包括下发给选手的和最终评测使用的），在OJ上运行所用的时间不会超过0.5s，运行所用的空间不会超过12MB，也就是说，选手实际可用的时间至少为0.5s，实际可用的空间至少为500MB。