%graph(G,V,E).
graph([V,E],V,E).
v([V,E],V).
e([V,E],E).
edge(G,X,Y):-e(G,E),member([X,Y],E).
path(G,X,X,P,P).
path(G,X,Y,P,R):-edge(G,X,Z),not(member(Z,P)),path(G,Z,Y,[Z|P],R).
path(G,X,Y,P):-path(G,X,Y,[X],R),reverse(P,R).
notconnected(G):-v(G,V),member(X,V),member(Y,V),not(path(G,X,Y,P)).
connected(G):-not(notconnected(G)).
cycled(G):-e(G,E),member([X,Y],E),path(G,Y,X,_).
istree(G):-connected(G),not(cycled(G)).
spantree(G,T):-v(G,V),e(G,E),subset(S,E),graph(T,V,S),istree(T).
subset([],S).
subset([H|T],S):-subset(T,S),member(H,S),not(member(H,T)).
%st(E,O,N,L).
st(E,O,[],[]).
st(E,O,N,[[X,Y]|H]):-member([X,Y],E),member(X,O),member(Y,N),remove(Y,N,N1),st(E,[Y|O],N1,L).
spantree1(G,T):-e(G,E),v(G,[X,V]),st(E,[X],V,E1),graph(T,[X|V],E1).