Given a simple undirected graph, please find the maximum k-core subgraph.

Input Format

Each line contains the edge given by a pair of node numbers (0, 1, 2, ..., n, n<1000), which is separated by a space.

Output Format

(Maximum number of k)-core

Edges sorted by vertex number

input 1 0 1 0 2 1 2 1 5 2 3 2 4 2 5 2 6 3 4 3 6 3 7 4 6 4 7 5 6 5 8 6 7 6 8 

a

output1:

3-core 2 3 2 4 2 6 3 4 3 6 3 7 4 6 4 7 6 7

input 2

0 1 0 2 0 3 0 4 0 5 0 6 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6

k

output:

6-core 0 1 0 2 0 3 0 4 0 5 0 6 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6

please solve using preferably C++ python or C, Java is not supported.