:- use_module(library(ugraphs)).                

main :-
	read_num(N),
	read_num(M),
        read_n_list(M, L),
        numlist(1, N, Vertices),
        vertices_edges_to_ugraph(Vertices, L, G),
        connected_vertices_by_list(G, N, VerticesList),
        graphs(L, VerticesList, Graphs),
        max_length(Graphs, Ans),
        write(Ans),
        nl,
        halt.

max_length([H|T], Max) :-
        length(H, HL),
        max_length(T, HL, Max).
max_length([], Max, Max).
max_length([H|T], NowMax, Max) :-
        length(H, HL),
        HL > NowMax ->
        max_length(T, HL, Max);
        max_length(T, NowMax, Max).
        
% グラフのリストを作る
graphs(AllVertexNeighborsPairList, VerticesList, Graphs) :-
        graphs(AllVertexNeighborsPairList, VerticesList, [], Graphs).
graphs(_, [], Acc, Acc).
graphs(AllVertexNeighborsPairList, [H|T], Acc, Graphs) :-
        make_graph(AllVertexNeighborsPairList, H, G),
        graphs(AllVertexNeighborsPairList, T, [G|Acc], Graphs).


connected_vertices_by_list(AllGraph, N, VerticesList) :-
        numlist(1, N, NumList),
        connected_vertices_by_list(AllGraph, NumList, [], VerticesList).
connected_vertices_by_list(_, [], Acc, Acc).
connected_vertices_by_list(AllGraph, [H|T], Acc, VerticesList) :-
        reachable(H, AllGraph, V),
        subtract(T, V, NewL),
        connected_vertices_by_list(AllGraph, NewL, [V|Acc], VerticesList).



% VerticesからなるグラフGを作る
make_graph(AllVertexNeighborsPairList, Vertices, G) :-
        vertex_neighbors_pair_from_vertex_list(AllVertexNeighborsPairList, Vertices, Pairs),
        vertices_edges_to_ugraph(Vertices, Pairs, G).

vertex_neighbors_pair_from_vertex_list(AllVertexNeighborsPair, Vertices, Pairs) :-
        vertex_neighbors_pair_from_vertex_list(AllVertexNeighborsPair, Vertices, [], Pairs).
vertex_neighbors_pair_from_vertex_list([], _, Acc, Acc).
vertex_neighbors_pair_from_vertex_list([V-N|T], Vertices, Acc, L) :-
        (
         member(V, Vertices),
         member(N, Vertices)
        )
        ->       
        vertex_neighbors_pair_from_vertex_list(T, Vertices, [V-N|Acc], L)
        ;
        vertex_neighbors_pair_from_vertex_list(T, Vertices, Acc, L).


read_n_list(N, L) :-
        read_n_list_aux(N, [], L).
read_n_list_aux(0, L, Reversed) :-
        reverse(L, Reversed).
read_n_list_aux(N, Acc, L) :-
        read_num(U),
        read_num(V),
        NewN is N - 1,
        read_n_list_aux(NewN, [U-V, V-U|Acc], L).

read_str(S) :-
        read_string(current_input, ' \n', '', _, S).

read_num(N) :-
	read_str(S),
	number_string(N, S).

