Antimatching

Vasya's older brother, Petya, attends an algorithm course in his school. Today he learned about matchings in graphs. Formally, a set of edges in a graph is called a *matching* if no pair of distinct edges in the set shares a common endpoint. Petya instantly came up with an inverse concept, an *antimatching*. In an antimatching, **any** pair of distinct edges should have a common endpoint. Petya