import java.io.*;
import java.text.*;
import java.util.*;

class VertexCoverTest
{
// This is the part of definition of vertices and function "compareTo"  
	static class MyVertex extends Vertex implements Sort.Comparable 
	{
   	public MyVertex(int r, int i)
	   {
	   super(r,i);					
	   }
	public int compareTo(Object other)		
	   {				
	   if( this.number() > (((MyVertex)other).number()) ) return 1;
	   else if( this.number() == (((MyVertex)other).number()) ) return 0;
	   else return -1;				
	   }
	}

// This is a routine for edge input 
	public static Edge readData() 
	{  
      int x;
	  int y; // the number we wish to read
      try
      {  InputStreamReader isr 
            = new InputStreamReader(System.in);
         BufferedReader br 
            = new BufferedReader(isr);
         String s = br.readLine(); 
		 StringTokenizer t= new StringTokenizer(s, " ");
		 x = Integer.parseInt(t.nextToken());
		 y = Integer.parseInt(t.nextToken());
	  }
      catch(IOException e)
      {  x = 0;
		 y = 0;
      }
	  Edge ed = new Edge(x,y);
	  return ed;
   }

// This is a routine for input of the number of vertex and edge
	public static int readint() 
	{
	  int a;
	  try
		{  InputStreamReader isr 
		= new InputStreamReader(System.in);
		BufferedReader br 
		= new BufferedReader(isr);
		String s = br.readLine(); 
		DecimalFormat df = new DecimalFormat();
		Number n = df.parse(s);
		a = n.intValue();
		}
	  catch(IOException e)
		{  a = 0;
		}
	  catch(ParseException e)
		{  a = 0;
		}
	  return a;
	}

// main method
   public static void main(String[] args) 
	{
		System.out.println("Input the number of vertex");
		int nv = readint();

		System.out.println("Input the number of edge");
		int ne = readint();

		Edge[] e = new Edge[ne];

		System.out.println("Enter edges");
		for (int i=0;i<ne ;i++ )
		{
			e[i] = readData();
		}

		int[] tmp = new int[nv+1];
		//initialization
		for (int i=0;i<nv ;i++ )
		{
			tmp[i]=0;
		}

		for (int i=0;i<nv ;i++ )
		{
			for (int j=0;j<ne ;j++ )
			{
				if ( ((i+1)==e[j].pred()) || ((i+1)==e[j].succ()) )
				{
					tmp[i] += 1;
				}
			}
		}

		MyVertex[] v = new MyVertex[nv];
		for (int i=0;i<nv ;i++ )
		{
			v[i] = new MyVertex(i+1,tmp[i]);
		}


		
// Input print
		for (int i=0;i<nv ;i++ )
		{
		System.out.println("\n vertex : " + v[i]);
		}
		for (int i=0;i<ne ;i++ )
		{
		System.out.println("\n edge : " + e[i]);
		}

// "Sort" is the function of searching the vertex with largest degree corresponds to 
// covering the largest edge subset with a single vertex.
		Sort.st(v);
// v[0] is the one.

// From this, main algorithm for search "Vertex Cover"

		int[] cover = new int[nv]; 
		for (int i=0;i<nv ;i++ )
		{
				for (int j=0;j<ne ;j++ )
				{	
						//If there are edges adjacentto v[0], add v[0] to the set of vertex cover.
						//And remove v[0] and edges incident to v[0].
						if ( (v[0].kind()==e[j].pred()) )
						{	
							for (int k=0;k<nv ;k++ )
							{
								if ( v[k].kind()==e[j].succ() )
								{ v[k]=new MyVertex( v[k].kind() , v[k].number()-1 );		}
							}
							// This is the part of adding v[0] to the set of vertex cover.
							cover[i] = v[0].kind();
							
							// This is the part of removing v[0] and edges incident to v[0].
							v[0] = new MyVertex(v[0].kind(),0);
							e[j] = new Edge(0,0);
						}
				

						// Similar to above description. 
						else if (  (v[0].kind()==e[j].succ()) )
						{	
							for (int k=0;k<nv ;k++ )
							{
								if ( v[k].kind()==e[j].pred() )
								{ v[k]=new MyVertex( v[k].kind() , v[k].number()-1 );		}
							}
							cover[i] = v[0].kind();
							v[0] = new MyVertex(v[0].kind(),0);
							e[j] = new Edge(0,0);
						}
				}
				//Now, the vertex with largest degree corresponds to covering the largest edge subset with a single vertex
				//is changed. Then we need to search new v[0].
				Sort.st(v);
		}

// Output(vertex cover set) print
		System.out.println("\n=======Vertex Cover=========");
		for (int i=0;i<nv ;i++ )
		{
			int j=i+1;
			if (cover[i]!= 0)
			{
				System.out.println("\n" + j + "th element : "  + cover[i]);
			}
		}
	}
}