:- use_module(library(ugraphs)).

read_number(In, Num) :-
	read_line_to_codes(In, Codes), number_codes(Num, Codes).

read_number2(In, X-Y) :- read_line_to_codes(In, C),
	append(C1, [0' |C2], C), number_codes(X, C1), number_codes(Y, C2).

read_match(N, Match) :- current_input(In),
	read_number(In, N), read_number(In, M),
	length(Match, M), maplist(read_number2(In), Match).

write_rank(Rank, Extra) :-
	maplist(writeln, Rank), writeln(Extra).

single_solution([_], _).
single_solution([X1,X2|Xs], Match) :-
	memberchk(X1-X2, Match), single_solution([X2|Xs], Match).

rank(N, Match, Rank) :- 
	numlist(1, N, L), vertices_edges_to_ugraph(L, Match, G), top_sort(G, Rank).

:-  setup_and_call_cleanup(see('input.txt'), read_match(N, Match), seen), 
	rank(N, Match, Rank), (single_solution(Rank, Match) -> Extra = 0; Extra = 1),
	setup_and_call_cleanup(tell('output.txt'), write_rank(Rank, Extra), told).