BZOJ3706 反色刷

Luogu

IDLGP10777

Time1000ms

Memory512MB

DifficultyP4

欧拉回路

给定 $n$ 个点，$m$ 条边的无向图，边有黑白两种颜色。现在你可以进行若干次回路反色操作，每次操作从任意点出发，每经过一条边，将其颜色反转，最后回到起点。判断能否通过若干次操作，使这张图所有边都变成白色。因为某种原因，边的颜色是会改变的，即你相当于需要支持以下两种操作： - `1 x` 将第 $x$ 条边反色（边的编号为 $0\sim m-1$）； - `2` 求出最少操作次数； ## Input 第一行两个整数 $n,m$ 表示这张图有 $n$ 个点 $m$ 条边。接下来 $m$ 行，每行 $3$ 个整数 $u,v,c$ 表示一条无向边和这条边的颜色，其中 $0$ 为白色，$1$ 为黑色。接下来一个整数 $q$，表示有 $q$ 个操作。接下来 $q$ 行操作，描述如上。 ## Output 对于每个询问，输出一行一个整数，表示最少需要的反色操作次数。如果没有合法方案输出 $-1$。 [samples] ## Note 数据保证，$1\leq n,m,q \leq 1000000$，$c < 2$，没有重边自环。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "BZOJ3706 反色刷",
    "description": {
      "content": "给定 $n$ 个点，$m$ 条边的无向图，边有黑白两种颜色。现在你可以进行若干次回路反色操作，每次操作从任意点出发，每经过一条边，将其颜色反转，最后回到起点。判断能否通过若干次操作，使这张图所有边都变成白色。 因为某种原因，边的颜色是会改变的，即你相当于需要支持以下两种操作： - `1 x` 将第 $x$ 条边反色（边的编号为 $0\\sim m-1$）； - `2` 求出最少操作次数；",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10777"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$ 个点，$m$ 条边的无向图，边有黑白两种颜色。现在你可以进行若干次回路反色操作，每次操作从任意点出发，每经过一条边，将其颜色反转，最后回到起点。判断能否通过若干次操作，使这张图所有边都变成白色。\n\n因为某种原因，边的颜色是会改变的，即你相当于需要支持以下两种操作：\n- `1 x` 将第 $x$ 条边反色（边的编号为 $0\\sim m-1$）；\n- `2` 求出最少操作次数；\n\n## ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments