선인장 혁명

전 지구적 재난 이후 지하 동굴에서 살아남은 도시 ACM(Advanced Cave Megapolis)이 있다. 동굴들은 통로로 연결되어 있으며, 도시 전체 지도는 동굴을 정점으로, 통로를 간선으로 하는 무향 그래프로 나타낼 수 있다.

이 동굴 도시에서 혁명이 일어났다. 도시의 전체 주민은 함께 따라야 할 공통 법률에 합의하지 못한 채 $k$개의 정당으로 균등하게 나뉘었고, 이들은 도시를 $k$개의 구역으로 나눈 뒤 각 구역의 주민이 원하는 법을 스스로에게 적용하기로 했다.

도시 지도가 그래프로 주어질 때, 이 그래프를 크기가 같은 $k$개의 구역으로 분할할 수 있는지 판별하여라. 각 구역은 연결된 부분그래프여야 한다. 즉, 그 구역을 이루는 정점 집합이 유도하는 부분그래프가 연결되어 있어야 한다.

정점의 수 $n$은 $k$로 나누어떨어지므로, 각 구역은 정확히 $n/k$개의 동굴을 포함해야 한다. 주어지는 지도는 항상 선인장(cactus) 그래프이다. 선인장이란 모든 간선이 많아야 하나의 단순 사이클에만 속하는 연결 무향 그래프로, 트리에 일부 사이클을 허용한 일반화라고 볼 수 있다.

첫째 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 50000$, $0 \le m \le 10000$, $1 \le k \le n$). $n$은 정점의 수이며 정점은 $1$번부터 $n$번까지 번호가 매겨진다. 그래프의 간선은 서로 겹치지 않는 여러 개의 경로로 주어지며, $m$은 그러한 경로의 개수, $k$는 나눌 구역의 수이다. $n$은 $k$로 나누어떨어진다.

이어지는 $m$개의 줄에는 각각 하나의 경로가 주어진다. 한 경로는 정수 $s_i$ ($2 \le s_i \le 1000$)로 시작하고, 그 뒤에 $1$ 이상 $n$ 이하의 정수가 $s_i$개 온다. 이 정수들은 경로가 지나는 정점을 순서대로 나타내며, 인접한 두 정점은 하나의 간선을 이룬다. 경로에서 이웃한 두 정점은 서로 다르다. 한 경로는 같은 정점을 여러 번 지날 수 있지만, 입력 전체에서 각 간선은 정확히 한 번만 등장하고 다중 간선은 없다(임의의 두 정점 사이에는 간선이 많아야 하나뿐이다).

입력으로 주어지는 그래프는 선인장이다.

도시를 각각 정확히 $n/k$개의 동굴로 이루어진 $k$개의 연결된 구역으로 분할할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.