Cactus Revolution

Advanced Cave Megapolis (ACM) is a city that survives in the underground caves left after a global catastrophe. The caves are connected by passages, and the entire city map can be represented as an undirected graph whose vertices are caves and whose edges are passages.

A revolution has broken out in the cave city. The whole population is split evenly into $k$ parties that cannot agree on the common laws they should all adopt. They decide to divide the city into $k$ districts and let the citizens of each district impose the laws of their liking upon themselves.

You are given the city map as a graph. Your task is to decide whether it can be partitioned into $k$ equally sized districts. Each district must be a connected subgraph, that is, a subset of the graph's vertices whose induced subgraph is connected.

The number of vertices $n$ is divisible by $k$, so every district must contain exactly $n/k$ caves. The map is guaranteed to be a cactus: a connected undirected graph in which every edge belongs to at most one simple cycle. Intuitively, a cactus generalizes a tree by allowing some cycles.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 50000$, $0 \le m \le 10000$, $1 \le k \le n$), where $n$ is the number of vertices. Vertices are numbered from $1$ to $n$. The edges are given as a set of edge-distinct paths, $m$ is the number of such paths, $k$ is the number of districts, and $n$ is divisible by $k$.

Each of the next $m$ lines describes one path. A path begins with an integer $s_i$ ($2 \le s_i \le 1000$) followed by $s_i$ integers between $1$ and $n$. These integers are the vertices visited by the path, in order, and each pair of adjacent vertices forms an edge. Consecutive vertices in a path are distinct. A path may pass through the same vertex several times, but across the whole input every edge is traversed exactly once, and there are no multiple edges (at most one edge between any two vertices).

The graph described by the input is a cactus.

Print YES if the city can be partitioned into $k$ connected districts of exactly $n/k$ caves each, and NO otherwise.