F. Bipartite Checking

Codeforces

IDCF813F

Time6000ms

Memory256MB

Difficulty—

data structuresdsugraphs

English · Original

Chinese · Translation

Formal · Original

You are given an undirected graph consisting of _n_ vertices. Initially there are no edges in the graph. Also you are given _q_ queries, each query either adds one undirected edge to the graph or removes it. After each query you have to check if the resulting graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color). ## Input The first line contains two integers _n_ and _q_ (2 ≤ _n_, _q_ ≤ 100000). Then _q_ lines follow. _i_th line contains two numbers _x__i_ and _y__i_ (1 ≤ _x__i_ < _y__i_ ≤ _n_). These numbers describe _i_th query: if there is an edge between vertices _x__i_ and _y__i_, then remove it, otherwise add it. ## Output Print _q_ lines. _i_th line must contain _YES_ if the graph is bipartite after _i_th query, and _NO_ otherwise. [samples]

给定一个包含 #cf_span[n] 个顶点的无向图。初始时图中没有边。同时给定 #cf_span[q] 个查询，每个查询要么添加一条无向边，要么删除它。在每次查询后，你需要判断所得图是否为二分图（即，能否将图的所有顶点染成两种颜色，使得没有任何一条边连接两个同色的顶点）。第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n, q ≤ 100000]）。接下来 #cf_span[q] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]）。这些数描述第 #cf_span[i] 个查询：如果顶点 #cf_span[xi] 和 #cf_span[yi] 之间存在边，则删除它；否则添加它。请输出 #cf_span[q] 行。第 #cf_span[i] 行必须包含 _YES_（如果第 #cf_span[i] 次查询后图是二分图），否则输出 _NO_。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n, q ≤ 100000]）。接下来 #cf_span[q] 行，每行包含两个数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[1 ≤ xi < yi ≤ n]）。这些数描述第 #cf_span[i] 个查询：如果顶点 #cf_span[xi] 和 #cf_span[yi] 之间存在边，则删除它；否则添加它。 ## Output 请输出 #cf_span[q] 行。第 #cf_span[i] 行必须包含 _YES_（如果第 #cf_span[i] 次查询后图是二分图），否则输出 _NO_。 [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ with $ 2 \leq n, q \leq 100000 $. Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, n\} $ and initially $ E = \emptyset $. Let $ Q = ((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q)) $ be a sequence of queries, where for each $ i \in \{1, \dots, q\} $, $ 1 \leq x_i < y_i \leq n $, and the $ i $-th query toggles the presence of edge $ \{x_i, y_i\} $ in $ E $. **Constraints** For all $ i \in \{1, \dots, q\} $: - $ 1 \leq x_i < y_i \leq n $ **Objective** After each query $ i \in \{1, \dots, q\} $, determine whether $ G $ is bipartite. Output "YES" if $ G $ is bipartite; otherwise output "NO".

Samples

Input #1

Output #1

YES
YES
NO
YES
NO

API Response (JSON)

{
  "problem": {
    "name": "F. Bipartite Checking",
    "description": {
      "content": "You are given an undirected graph consisting of _n_ vertices. Initially there are no edges in the graph. Also you are given _q_ queries, each query either adds one undirected edge to the graph or remo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF813F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected graph consisting of _n_ vertices. Initially there are no edges in the graph. Also you are given _q_ queries, each query either adds one undirected edge to the graph or remo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 #cf_span[n] 个顶点的无向图。初始时图中没有边。同时给定 #cf_span[q] 个查询，每个查询要么添加一条无向边，要么删除它。在每次查询后，你需要判断所得图是否为二分图（即，能否将图的所有顶点染成两种颜色，使得没有任何一条边连接两个同色的顶点）。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[q]（#cf_span[2 ≤ n, q ≤ 10000...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ with $ 2 \\leq n, q \\leq 100000 $.  \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, \\dots, n\\} $ and initially $ E = \\emptyset $.  \nLet $ Q...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments