Maximum Connected d-Core Subgraph

Given a simple undirected graph \( G=(V,E) \) with \( n \) vertices (numbered from 1 to \( n \)) and \( m \) edges, and a positive integer \( d \), select a subset \( S \subseteq V \) with the maximum possible size such that:

• For every vertex \( u\in S \), its number of neighbors within \( S \) is at least \( d \), i.e., \( \sum_{v\in S} [ (u,v)\in E] \ge d \).
• The induced subgraph on \( S \) is connected.

If no such subset exists, output -1.

The induced subgraph of a subset \( V'\subseteq V \) is defined as \( G'=(V',E') \) where \( E' = \{ (u,v) \in E : u\in V' \text{ and } v\in V' \} \).

inputFormat

The input consists of:

n m d
u1 v1
nu2 v2
... 
num vm

where the first line contains three integers \( n \), \( m \) and \( d \). Following are \( m \) lines each containing two integers \( u \) and \( v \) representing an edge between vertices \( u \) and \( v \).

outputFormat

If a valid subset \( S \) exists, output two lines. The first line contains a single integer \( k=|S| \), and the second line contains the \( k \) vertices in \( S \) in increasing order separated by spaces. Otherwise, output a single line with -1.

sample

5 5 1
1 2
2 3
3 4
4 5
2 5

5
1 2 3 4 5