两色徽章¶

背景故事¶

手工展览准备给每位参展者发一枚红色或蓝色徽章。徽章还没发，意见箱先满了：“我俩绝对不能撞色！”

组织者按收到的顺序处理这些要求。只要还能找到一种配色，满足此前已接受的全部要求和新要求，就答应下来；否则只好把新要求退回。有人甚至在纸条上把自己的名字填了两遍，组织者决定照章办理。

采购员倒是很高兴：红色徽章正在打折。每处理完一张纸条，他都想知道，在满足所有已接受要求的前提下，最多能发出多少枚红色徽章。

(本故事由GPT-6 Sol重写)

有 \(n\) 个顶点，初始没有边。依次给出 \(m\) 个无向边请求 \((u,v)\) . 若将该边加入当前图后图仍是二分图，则接受该请求并保留这条边；否则拒绝，当前图不变。允许自环和重复请求。

合法二染色是指为每个顶点指定颜色 \(0\) 或 \(1\) ，使每条边的两个端点颜色不同。每次请求后，输出该请求是否被接受，以及当前图的所有合法二染色中，颜色 \(0\) 的顶点数的最大值。每次都可以重新选择配色，不必沿用上一次的方案。

第一行两个整数 \(n,m\) .

接下来 \(m\) 行，每行两个整数 \(u,v\) ，表示一条边请求。

对每个请求输出一行两个整数。第一个整数为 \(1\)（接受）或 \(0\)（拒绝），第二个整数为最多能染成颜色 \(0\) 的顶点数。

第三条边会与前两条边构成奇环，因此被拒绝。最后所有顶点连成一个分量，其两个颜色类的大小分别为 \(3\) 和 \(2\) .

0 1
0 1
0 1