408806: GYM103328 C Perfect Cactus

Do you know what a perfect graph is? Before we can talk more about it, let's first define a few terms. Let $$$G$$$ be an undirected simple graph. The set of vertices in $$$G$$$ is denoted as $$$V(G)$$$. The set of edges in $$$G$$$ is denoted as $$$E(G)$$$. The complement of $$$G$$$, denoted as $$$\bar{G}$$$, is a graph containing all edges that do not appear in $$$E(G)$$$. A subgraph $$$G^\prime$$$ of $$$G$$$ is an induced subgraph if all edges $$$(u, v)$$$ such that $$$u, v \in V(G^\prime)$$$ belong to $$$E(G^\prime)$$$. The clique number $$$\omega(G)$$$ is the size of the maximum clique. That is, the size of the maximum subset $$$S$$$ of vertices such that every two vertices in $$$S$$$ are adjacent. The chromatic number $$$\chi(G)$$$, on the other hand, represents the minimum number of colors required to color $$$V(G)$$$ such that for every two adjacent vertices $$$x$$$ and $$$y$$$, $$$x$$$ has a different color than $$$y$$$ does.

One can easily see that $$$\chi(G) \geq \omega(G)$$$ for all graphs $$$G$$$, because you need at least $$$\omega(G)$$$ colors to color the maximum clique. Therefore, graphs that have the property of $$$\chi(G) = \omega(G)$$$ seem special and worth studying. It's tempting to call such graphs perfect. However, you can easily construct a graph $$$G_1$$$ with $$$\chi(G_1) > \omega(G_1)$$$ and put it beside a clique $$$G_2$$$ of $$$\chi(G_1)$$$ vertices. This results in a seemingly perfect graph $$$G = G_1 \cup G_2$$$ with $$$\chi(G) = \omega(G)$$$. This is not what we want. Therefore, we instead say that a graph $$$G$$$ is perfect if, for all induced subgraphs $$$G^\prime$$$ of $$$G$$$, the clique number of $$$G^\prime$$$ equals the chromatic number of $$$G^\prime$$$.

Now, the question comes. What types of graphs are perfect and what are not? A simple example of non-perfect graphs is $$$C_5$$$, a cycle of length $$$5$$$: $$$C_5$$$ has clique number $$$2$$$, but in order to color it properly, you need at least $$$3$$$ colors. Obviously, all odd cycles of length at least $$$5$$$ are not perfect for similar reasons. These cycle graphs are called odd holes. Similarly, one can see that the complements of odd holes are not perfect as well. These graphs are called odd antiholes.

In addition to odd holes and odd antiholes, if a graph $$$G$$$ contains an induced subgraph isomorphic to an odd hole or an odd antihole, then $$$G$$$ is not a perfect graph according to the definition. Thus, we've now found some examples of non-perfect graphs. But what about graphs without odd holes and odd antiholes? Will such graphs ever be non-perfect? Mathematician Berge conjectured that these are all the non-perfect graphs in 1961. That is, a graph is perfect if and only if it does not contain an induced subgraph isomorphic to an odd hole or an odd antihole. In 2002, Chudnovsky et al. proved the conjecture and showed that there's no such exception. This phenomenal theorem is what we now know as the Strong Perfect Graph Theorem (the word strong is used to distinguish between the (weak) perfect graph theorem, which states that a graph $$$G$$$ is perfect if and only if its complement $$$\bar{G}$$$ is perfect. It's easy to show that the (weak) perfect graph theorem can be immediately inferred from the strong perfect graph theorem).

Are you still looking for the problem to solve? Here it is. Given a cactus, determine if it's perfect or not. A cactus is a connected simple graph in which every edge belongs to at most one simple cycle.

The first line of the input contains two integers $$$N$$$ and $$$M$$$ — the number of vertices and the number of edges.

$$$M$$$ lines follow, and the $$$i$$$-th of which contains two integers $$$u_i$$$ and $$$v_i$$$, denoting the endpoints of the $$$i$$$-th edge.

• $$$1 \leq N \leq 10^5$$$
• $$$1 \leq u_i \neq v_i \leq N$$$
• It's guaranteed that the input graph is a cactus

If the input cactus is perfect, print Yes. Otherwise, print No.

5 5
1 2
2 3
3 4
4 5
5 1

No

5 4
1 2
2 3
3 4
4 5

Yes