[AdditionalFile4903.zip](file://AdditionalFile4903.zip?type=additional_file)

P5966 [POI 2016] Hydrorozgrywka

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图，保证每条边属于且只属于一个环。

两个人在这张图上玩游戏，一开始他们会在某个节点放一个棋子，然后依次移动这个棋子，已经走过的边不能再走，谁不能移动谁就输了。

请求出所有先手必胜的策略中游戏开始时放棋子的位置。

输入格式

第一行包含两个正整数 $n,m$，表示点数和边数。

接下来 $m$ 行每行包含两个正整数 $a,b$，表示 $a$ 点到 $b$ 点之间有一条无向边。

输出格式

包含 $n$ 行，对于第 $i$ 行，如果在 $i$ 点放棋子先手必胜，输出 1，否则输出 2。

输入输出样例 #1

输入 #1

6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 3

输出 #1

1
1
1
2
1
2

说明/提示

对于 $100\%$ 的数据，$3\le n,m\le 5 \times 10^5$，$1\le a,b\le n$，$a\ne b$。

#4903. 「POI2016 R1」水管比赛 Hydrocontest

标签: 传统 | 时间限制: 8000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Hydrorozgrywka

Bajtazar 和 Bajtoni 的管道施工队中标了为下字节村铺设水管的工程。当地的路网由 $n$ 个路口通过 $m$ 条道路连接，任何两个路口都能通过路网连通。每条道路下都需要埋设水管。下字节村的所有道路均为双向，路口之间可双向通行。

为了让工作更有趣，Bajtazar 和 Bajtoni 决定玩个游戏。游戏开始时，两人的施工队站在同一个路口，之后始终一起行动。他们轮流操作，从 Bajtazar 开始。每轮，玩家选择一条从当前路口出发、尚未埋管的新道路。玩家的施工队在这条路下埋管，然后两队一起移动到道路另一端的路口。

无法行动的玩家输掉游戏，作为惩罚，他的施工队得埋设剩余道路的水管。Bajtazar 想知道，从哪些路口开始游戏，他能保证无论 Bajtoni 怎么行动都能赢。他请你帮忙列出这些路口。此外，他发现下字节村的路网有个有趣特性：从任意道路中点出发，不回头且不重复经过任何路口，只有一条路径能绕个圈回到起点。

输入格式

输入第一行包含两个整数 $n$ 和 $m$，分别表示路口数和道路数。路口编号从 $1$ 到 $n$。

接下来的 $m$ 行描述路网，每行两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示 $a$ 号和 $b$ 号路口间有一条道路。任意两路口间至多有一条道路。

输出格式

输出 $n$ 行，第 $i$ 行包含一个数字：若从 $i$ 号路口开始 Bajtazar 能保证获胜，输出 $1$；否则输出 $2$。

样例

输入

6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 3

输出

1
1
1
2
1
2

附加样例

1. $n=9, m=12$，路网由四个圈组成：$1-2-3-1$、$1-4-5-1$、$1-6-7-1$、$1-8-9-1$；
2. $n=998, m=999$，每对相邻路口 $j$ 和 $j+1$ $(1 \leq j < n)$ 有道路，另有道路连接 $1$ 与 $499$、$499$ 与 $998$；
3. $n=500000, m=500000$，路网形成一个大圈。

数据范围与提示

详细子任务附加限制及分值如下表所示。