/* cs */

/* 
 * Problem  : 	EXAM
 * Contest  : 	UOI-2006 (Dnepropetrovsk)
 * Type     : 	Solution
 * Date     : 	March 30, 2006
 * Author   : 	Shamil Yagiyayev
 * Language :	C#
 * Compiler :	.NET 1.1
 * Algorithm:	Author Solution. This solution also processes multiple tests, generates statistics and draws the tests.
 */

#define DRAW

using System;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;

public class Person
{
	// public static bool Boy;
	public bool[] Adjacents = new bool[Exam.MAX_CLASS]; 
	public int Rich = 0;
}

public class Exam
{
	static /*readonly*/ string SUMMARY = "exam-tests.csv";

	static /*readonly*/ string FILE_IN = "exam.dat";
	static /*readonly*/ string FILE_OUT = "exam.sol";
	static /*readonly*/ string DRAW_OUT = "exam-draw.txt";

	static StreamWriter draw; 

	public static int MAX_CLASS = 51;
	static int N;
	static int M;

	static Person[] group;

	static int[] path;
	static int pathSize;
	static bool pathFound;
	static bool[] visited;

	static int manyLengthenings = 0;
	static int manyLongLengthenings = 0;

#if DRAW

	static bool[] boygirl = new bool[MAX_CLASS+1];
	static void DrawPicture(string status)
	{
		int[] bg = new int[N+1];
		int b=0; 
		int g=0;
		for (int i=1; i<=N; i++) 
			if (boygirl[i]) bg[i] = ++b; else bg[i] = ++g;

		draw.WriteLine("//-------- {0} ------------", status);

		// Draw Vertex
		for (int i=1; i<=N; i++)
			draw.WriteLine("DrawVertex(visioApp, {0}, {1}, {2});", i, boygirl[i]?0:1, bg[i]);

		// Draw Edges
		for (int i=1; i<=N; i++)
			if (boygirl[i])
				for (int j=1; j<=N; j++)
					if (group[i].Adjacents[j] && group[i].Rich != j)
						draw.WriteLine("DrawEdge(visioApp, {0}, {1});", bg[i], bg[j]);

		// Draw Rich Edges
		for (int i=1; i<=N; i++)
			if (boygirl[i])
				if (group[i].Rich != 0)
						draw.WriteLine("DrawRichEdge(visioApp, {0}, {1});", bg[i], bg[group[i].Rich]);
	}
#endif

	static int isolated;
	static bool[] iso;
	static int nBoys, nGirls;
	static void ReadData()
	{
		StreamReader sr = new StreamReader(FILE_IN);
		string[] line = (sr.ReadLine()).Split(new char[] {' '});
		N = int.Parse(line[0]);
		M = int.Parse(line[1]);
		group = new Person[N+1];
		iso = new bool[N+1];
		boygirl = new bool[N+1];
		for (int i=1;i<=N; i++) group[i] = new Person();

		for (int i=0; i<M; i++)
		{
			line = (sr.ReadLine()).Split(new char[] {' '});
			int a = int.Parse(line[0]);
			int b = int.Parse(line[1]);
			iso[a] = true;
			iso[b] = true;
			group[a].Adjacents[b] = true;
			group[b].Adjacents[a] = true;
			#if DRAW
			boygirl[a] = true;
			boygirl[b] = false;
			#endif
		}

		isolated = 0;
		for (int i=1; i<N+1; i++) if (!iso[i]) isolated++;
		
		nBoys=0; nGirls=0;
		for (int i=1; i<N+1; i++) if (boygirl[i]) nBoys++; else if (iso[i]) nGirls++;

	}
	static void InvertPath()
	{
		int prev = path[0];
		for (int i=1; i<pathSize; i++)
		{
			int curr = path[i];
			if (i % 2 != 0)
			{
				// not rich -> rich
				group[prev].Rich = curr;
				group[curr].Rich = prev;
			}
			else
			{
				group[curr].Rich = 0;
			}
			prev = curr;
		}
	}

	static void BuildLengtheningPath(int curr, int depth)
	{
		if (pathFound) return;

		visited[curr] = true;

		
		if (depth % 2 == 0)
		{
			// we need to select the rich edge
			int next = group[curr].Rich;

			if ( /*next == 0 ||*/ visited[next]) return;
			path[depth] = next;
			BuildLengtheningPath(next, depth+1);
		}
		else
		{
			for (int next=1; next<=N; next++)
				if (group[curr].Adjacents[next] && ! visited[next])
				{
					path[depth] = next;
					if (group[next].Rich > 0)
					{
						BuildLengtheningPath(next, depth+1);
						if (pathFound) return;
					}
					else
					{
						// Path Found!
						pathSize = depth+1;
						pathFound = true;
						return;
					}
					
				}
		}
	}

	static void BuildLexicalLengtheningPath(int initial, int curr, int depth)
	{
		if (pathFound) return;

		visited[curr] = true;

		if (depth % 2 == 0)
		{
			// we need to select the rich edge
			int next = group[curr].Rich;

			if ( visited[next] ) return;
			path[depth] = next;

			if (initial < next)
			{
				// Path Found!
				pathSize = depth+1;
				pathFound = true;
				return;
			}
			else
			{
				BuildLexicalLengtheningPath(initial, next, depth+1);
			}
		}
		else
		{
			for (int next=1; next<=N; next++)
				if (group[curr].Adjacents[next] && ! visited[next])
				{
					path[depth] = next;
					Debug.Assert(group[next].Rich > 0);
					BuildLexicalLengtheningPath(initial, next, depth+1);
					if (pathFound) return;
				}
		}
	}

	static void BuildMatching()
	{
		// select the base 
		bool canImprove = true;
		while (canImprove)
		{
			canImprove = false;
			for (int i=1; i<=N; i++)
				if (group[i].Rich == 0)
				{
					pathFound = false;
					path = new int[N];
					path[0] = i;
					visited = new bool[N+1];
					BuildLengtheningPath(i, 1);
					if (pathFound)
					{
						canImprove = true;
						manyLengthenings++;
						if (pathSize > 2) manyLongLengthenings++;
						InvertPath();
					}
				}
		}
	}


	static bool lexicalBetter = false;
	static void BuildLexicalMatching()
	{
		for (int i=1; i<=N; i++)
			if (group[i].Rich == 0)
			{
				pathFound = false;
				path = new int[N];
				path[0] = i;
				visited = new bool[N+1];
				BuildLexicalLengtheningPath(i, i, 1);
				if (pathFound) 
				{
					InvertPath();
					lexicalBetter = true;
				}
			}
	}


	static int answer = 0;
	static void WriteSolution()
	{
		StreamWriter sw = File.CreateText(FILE_OUT);
		bool was = false;
		for (int i=1; i<=N; i++)
			if (group[i].Rich > 0)
			{
				if (boygirl[i]) answer++;
				sw.Write("{0}{1}", was? " " : "", i);
				// if (boygirl[i]) sw.WriteLine("{0} {1}", i, group[i].Rich);
				was = true;
			}
		sw.WriteLine();

		/* for (int i=1; i<=N; i++)
			if (group[i].Rich > 0)
				sw.WriteLine("{0} -> {1}", i, group[i].Rich);
		*/
		sw.Close();
	}

	static void Main(string[] args)
	{
		string FILE_IN_REGEX;
		string FILE_OUT_FORMAT;
		Regex r;
		if ( args.Length == 0 )
		{
			FILE_IN_REGEX = "exam\\.dat";
			r = new Regex(FILE_IN_REGEX);
			FILE_OUT_FORMAT = "exam.sol";
			DRAW_OUT = "exam-draw.txt";
		}
		else
		{
			FILE_IN_REGEX = args[0];
			r = new Regex(FILE_IN_REGEX);
			FILE_OUT_FORMAT = args[1];
			DRAW_OUT = "exam.{0}.draw.txt";
		}

		StreamWriter sw = File.CreateText(SUMMARY);
		sw.WriteLine("File;N;M;Lengthenings;Long;boys;girls;neutral;need lex");

		DirectoryInfo di = new DirectoryInfo(Environment.CurrentDirectory);
		FileInfo[] fi = di.GetFiles();
		Match m;
		foreach (FileInfo fiTemp in fi)
			if ((m = r.Match(fiTemp.Name)).Success)
			{
				answer = 0;
				manyLengthenings = 0;
				manyLongLengthenings = 0;
				lexicalBetter = false;

				FILE_IN = fiTemp.Name;
				string test = m.Groups[1].ToString();
				FILE_OUT = String.Format(FILE_OUT_FORMAT, test);
				draw = File.CreateText(String.Format(DRAW_OUT, test));

				ReadData();
				DrawPicture("Initial");
				BuildMatching();
				DrawPicture("After Matching");
				BuildLexicalMatching();
				DrawPicture("After Lexical");
				WriteSolution();
				sw.Write("{0};", fiTemp.Name); // filename
				sw.Write("{0};", N); // N
				sw.Write("{0};", M); // M
				// boys
				//sw.Write("{0};", answer);  // Weight
				sw.Write("{0};", manyLengthenings); // manyLengthenings
				sw.Write("{0};", manyLongLengthenings); // manyLongLengthenings
				sw.Write("{0};", nBoys); // boys
				sw.Write("{0};", nGirls); // girls
				sw.Write("{0};", isolated); // neutral
				sw.Write("{0};", lexicalBetter); // neutral
				sw.WriteLine();
				draw.Close();
			}
		sw.Close();
	}
}