# 两色徽章

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整。
- 内存限制：512 MB

## 背景故事

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

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

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

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

## 形式化问题描述

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

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

## 输入格式

第一行两个整数 $n,m$ .

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

## 输出格式

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

## 样例 1

### 输入

```text
5 5
1 2
1 3
2 3
4 5
4 1
```

### 输出

```text
1 4
1 4
0 4
1 3
1 3
```

### 解释

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

## 样例 2

### 输入

```text
1 3
1 1
1 1
1 1
```

### 输出

```text
0 1
0 1
0 1
```

## 数据范围与保证

- $1\le n,m\le 500\,000$ .
- $1\le u,v\le n$ ；允许 $u=v$ 和重复边。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $n,m\le 15$ |
| 30% | $n,m\le 5\,000$ |
| 40% | 无额外条件 |