306906: CF1268E. Happy Cactus

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Happy Cactus

题意翻译

给定一张仙人掌图,第 $i$ 条边连接 $u,v$,边权为 $i$ 定义路径为 "Happy Path" 当且仅当其满足沿途边权递增。 定义点对 $(u,v)$ Happy 当且仅当存在一条 Happy Path 以 $u$ 为起点,$v$ 为终点。 对于 $u=1,2...n$,求满足 $(u,v)$ Happy 的 $v$ 的数量。 Translated by EmptySoulist $n,m\le 5\cdot 10^5$

题目描述

You are given a cactus graph, in this graph each edge lies on at most one simple cycle. It is given as $ m $ edges $ a_i, b_i $ , weight of $ i $ -th edge is $ i $ . Let's call a path in cactus increasing if the weights of edges on this path are increasing. Let's call a pair of vertices $ (u,v) $ happy if there exists an increasing path that starts in $ u $ and ends in $ v $ . For each vertex $ u $ find the number of other vertices $ v $ , such that pair $ (u,v) $ is happy.

输入输出格式

输入格式


The first line of input contains two integers $ n,m $ ( $ 1 \leq n, m \leq 500\,000 $ ): the number of vertices and edges in the given cactus. The next $ m $ lines contain a description of cactus edges, $ i $ -th of them contain two integers $ a_i, b_i $ ( $ 1 \leq a_i, b_i \leq n, a_i \neq b_i $ ). It is guaranteed that there are no multiple edges and the graph is connected.

输出格式


Print $ n $ integers, required values for vertices $ 1,2,\ldots,n $ .

输入输出样例

输入样例 #1

3 3
1 2
2 3
3 1

输出样例 #1

2 2 2 

输入样例 #2

5 4
1 2
2 3
3 4
4 5

输出样例 #2

4 4 3 2 1 

Input

题意翻译

给定一张仙人掌图,第 $i$ 条边连接 $u,v$,边权为 $i$ 定义路径为 "Happy Path" 当且仅当其满足沿途边权递增。 定义点对 $(u,v)$ Happy 当且仅当存在一条 Happy Path 以 $u$ 为起点,$v$ 为终点。 对于 $u=1,2...n$,求满足 $(u,v)$ Happy 的 $v$ 的数量。 Translated by EmptySoulist $n,m\le 5\cdot 10^5$

加入题单

上一题 下一题 算法标签: