**PROBLEM LINK:** Problem

**Author and editorialist**: Denis Anishchenko

**Tester**: Hasan Jaddouh

**DIFFICULTY**: Medium

**PREREQUISITES**: Constructive, graphs

**EXPLANATION**:

Let’s consider vertex v with minimal degree (degree is number of neighbors). If degree(v) < k, than we have found a good cut: we can choose A = \{v\}. Otherwise, for all vertices v is true that degree(v) \geq k. Let’s go from vertex v in neighbor u, if it’s not visited earlier, after that, go from u to not visited vertex w and so on. In some moment we will have the situation that all neighbors of some vertex f is visited earlier, let’s consider neighbor which we have visited earlier than another ones (u). It’s clear that path between u and f through visited vertices and edge (u, v) forms a correct simple cycle.