:- use_module(library(lists), [member/2]).
:- use_module(contestlib, [sublist/2]).

spanspid :-
	findall(edge(X,Y),edge(X,Y),AllEdges),
	setof(X,is_node_in(X,AllEdges),AllNodes),
	AllNodes = [_|OneLess],
        length(OneLess,Len),
	length(SubGraph,Len),
	sublist(AllEdges,SubGraph),
	setof(X,is_node_in(X,SubGraph),NodesSubGraph),
	NodesSubGraph = AllNodes,
	findall(Node,bigdegree_node(SubGraph,Node,AllNodes),BigDegrees),
	sort(BigDegrees,BigDegreesUnique),
	BigDegreesUnique \= [_,_|_],
	!.

bigdegree_node(SubGraph,Node,Nodes) :-
	member(Node,Nodes),
	setof(Connected,connected(Node,Connected,SubGraph),ListConnected),
	ListConnected = [_,_,_|_].

connected(N1,N2,Edges) :- member(edge(N1,N2),Edges).
connected(N1,N2,Edges) :- member(edge(N2,N1),Edges).

is_node_in(Node,Edges) :- connected(Node,_,Edges).