CF1391E Pairs of Pairs

You have a simple and connected undirected graph consisting of $ n $ nodes and $ m $ edges. Consider any way to pair some subset of these $ n $ nodes such that no node is present in more than one pair. This pairing is valid if for every pair of pairs, the induced subgraph containing all $ 4 $ nodes, two from each pair, has at most $ 2 $ edges (out of the $ 6 $ possible edges). More formally, for any two pairs, $ (a,b) $ and $ (c,d) $ , the induced subgraph with nodes $ \{a,b,c,d\} $ should have at most $ 2 $ edges. Please note that the subgraph induced by a set of nodes contains nodes only from this set and edges which have both of its end points in this set. Now, do one of the following: - Find a simple path consisting of at least $ \lceil \frac{n}{2} \rceil $ nodes. Here, a path is called simple if it does not visit any node multiple times. - Find a valid pairing in which at least $ \lceil \frac{n}{2} \rceil $ nodes are paired. It can be shown that it is possible to find at least one of the two in every graph satisfying constraints from the statement.

N/A

N/A

The path outputted in the first case is the following. The pairing outputted in the second case is the following. Here is an invalid pairing for the same graph — the subgraph $ \{1,3,4,5\} $ has $ 3 $ edges. Here is the pairing outputted in the third case. It's valid because — - The subgraph $ \{1,8,2,5\} $ has edges ( $ 1 $ , $ 2 $ ) and ( $ 1 $ , $ 5 $ ). - The subgraph $ \{1,8,4,10\} $ has edges ( $ 1 $ , $ 4 $ ) and ( $ 4 $ , $ 10 $ ). - The subgraph $ \{4,10,2,5\} $ has edges ( $ 2 $ , $ 4 $ ) and ( $ 4 $ , $ 10 $ ). Here is the pairing outputted in the fourth case.