// Arup Guha
// 11/18/2012
// Solution to 2012 South East Regional (D2) Problem D: Dueling Philosophers

import java.util.*;

public class d {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		int n = stdin.nextInt();
		int numE = stdin.nextInt();

		while (n != 0) {

			// Set up ordering matrix.
			boolean[][] canFollow = new boolean[n][n];
			for (int i=0; i<n; i++) {
				Arrays.fill(canFollow[i], false);
				canFollow[i][i] = true;
			}

			// Put in illegal "edges".
			for (int i=0; i<numE; i++) {
				int prev = stdin.nextInt();
				int next = stdin.nextInt();
				canFollow[prev-1][next-1] = true;
			}

			// Run a topological sort.
			topSort prob = new topSort(canFollow);
			boolean canDo = prob.runAlg();

			// We can do our tasks.
			if (canDo) {

				// Output appropriately.
				if (prob.hasMoreThanOne())
					System.out.println("2");
				else
					System.out.println("1");
			}

			// Can't do it.
			else {
				System.out.println("0");
			}

			n = stdin.nextInt();
			numE = stdin.nextInt();
		}
	}

}

class topSort {

	// Easier to run our sort storing all this stuff in an object.
	public int[] ordering;
	public boolean[] used;
	public int n;
	public int fillSpot;
	public boolean[][] dependency;
	public boolean branch;

	// Set everything up to fill the array from the end.
	public topSort(boolean[][] canFollow) {
		n = canFollow.length;
		used = new boolean[n];
		ordering = new int[n];
		fillSpot = n-1;
		dependency = canFollow;
	}

	// Here is our topological sort...
	public boolean runAlg() {

		Arrays.fill(used, false);
		fillSpot = n-1;
		for (int i=0; i<n; i++) {

			if (!used[i]) {
				// This means our DFS failed, so we can place item i.
				boolean flag = dfs(i);
				if (!flag)
					return false;
			}
		}
		return true;
	}

	// Must be called AFTER runAlg. Determines if any adjacent items can be swapped.
	// If so, there is more than one topological sort. If not, no changes can be made.
	public boolean hasMoreThanOne() {

		// Look for adjacent items to swap.
		for (int i=0; i<n-1; i++)
			if (!dependency[ordering[i]][ordering[i+1]])
				return true;

		// None found.
		return false;
	}

	// Runs a modified DFS on node.
	public boolean dfs(int node) {

		// Mark us.
		used[node] = true;

		// Go through all possible unused neighbors.
		for (int i=0; i<n; i++) {
			if (!used[i] && dependency[node][i]) {
				boolean flag = dfs(i);
				if (!flag)
					return false;
			}
		}

		// Return false if this node conflicts with what's been filled in.
		if (conflict(node))
			return false;

		// We can fill this spot in.
		ordering[fillSpot] = node;
		fillSpot--;
		return true;
	}

	// Returns true if node can't be placed before the nodes already placed.
	public boolean conflict(int node) {
		for (int i=fillSpot+1; i<n; i++)
			if (dependency[ordering[i]][node])
				return true;

		return false;
	}
}