以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

可复制的 PDF 提取文本
ICPC 2024–2025, NERC – Northern Eurasia Finals
St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024
Problem C. Cactus without Bridges
Time limit: 3 seconds
Memory limit: 1024 megabytes
Caroline asked you for help in solving a cactus problem one year ago. During the last year, she researched
extensively about cactuses. Today, she is the one presenting the problem.
You are given a cactus without bridges and also the length of each odd simple cycle is greater
than or equal to the number of odd simple cycles in cactus. Your task is to answer whether it’s
possible to label the cactus edges with positive integers such that the following conditions are satisfied:
• Let’s define the maximum label with t. All the integers 1, 2, . . ., t are used in labeling (note that
you do not need to minimize or maximize the value of t);
• For each vertex v of the given cactus, the labels of edges incident to the vertex v should be different
and should form an interval of consecutive integers.
An edge in the graph is called bridge if the deletion of that edge increases the number of connected
components of the graph. A cactus is a connected undirected graph in which every edge lies on at most
one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges
(multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed
in a cactus.
Input
The first line contains two integers n and m (3 ≤n ≤105, n ≤m ≤⌊3(n−1) ⌋) — the number of vertices 2
and edges in the cactus. Each of the next m lines contains two integers u and v (1 ≤u, v ≤n; u ̸= v) —
the edges of the cactus. The given cactus satisfies all constraints from the problem statement.
Output
If finding the labeling satisfying the problem’s conditions is impossible, output the single line with the
word “NO”. Otherwise, in the first line output the single word “YES”. In the second line output an integer
t (1 ≤t ≤m) — the number of different labels. In the third line output should contain m integers ci
(1 ≤i ≤m, 1 ≤ci ≤t) — the labels of the edges.
Examples
standard input standard output Illustration
5 5 NO 2
1 2
3
2 3
3 4 1
4 5
5 1 4
5
8 10 YES
1 1 2
1 2 4 2 4
2 3 1 2 3 2 4 3 1 2 3 2 3 4
2 3 1 3
1 4 3 5
1 5 1 2
4 5 6 8
5 6
2 3 6 7
7 8 7
8 5
Page 4 of 19