Edge Labeling of Cactus Graphs

Caroline has returned with an intriguing cactus problem. You are given a cactus graph (a connected undirected graph in which every edge lies on at most one simple cycle) that does not have any bridges (an edge whose removal increases the number of connected components), and in which the length of every odd simple cycle is at least \(k\), where \(k\) is the total number of odd simple cycles in the cactus.

Your task is to determine whether it is possible to label each edge of the cactus with a positive integer such that the following conditions hold:

• Let \(t\) be the maximum label used. All integers \(1,2,\ldots,t\) are used in the labeling (there is no requirement to minimize or maximize \(t\)).
• For every vertex \(v\) of the cactus, if we collect the labels of all edges incident to \(v\), they are all distinct and form a consecutive interval of integers (i.e. if \(v\) has degree \(d\), then the labels form \( [x, x+1, \ldots, x+d-1]\) for some positive integer \(x\)).

Recall that an edge is called a bridge if its removal increases the number of connected components of the graph. A cactus is a generalization of a tree which allows some cycles, provided that any edge is contained in at most one simple cycle. Multiedges and loops are not allowed.

Based on the above, output YES if it is possible to label the edges as required, or NO otherwise.

Note: In all input cases for this problem the graph will always be a cactus without bridges and will satisfy the odd cycle condition.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\) representing the number of vertices and edges in the graph, respectively.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1 \leq u, v \leq n)\) indicating that there is an edge connecting vertices \(u\) and \(v\). It is guaranteed that the graph is a cactus, contains no bridges, and satisfies the condition that for every odd simple cycle, its length is at least the total number of odd simple cycles in the graph.

outputFormat

Output a single line containing YES if it is possible to perform such an edge labeling, or NO otherwise.

sample

3 3
1 2
2 3
3 1

YES