LanX! Quoting wikipedia:

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Of course it can be done in perl! For a sample problem such as given, here's a sample solution.

#! /usr/bin/perl

chomp ((undef, my @D) = <DATA>);
(my $Q = pop @D) =~ s/ /\\b.+\\b/;

sub xt { grep s/\b(\d+),\1\b/$1/, map qq/$_[0],$_/, @_ }
sub tx { print,exit for grep /^$Q$/, @_; map {xt $_, @_} @_ }

push @D, tx @D for \(@D);

__DATA__
5 6
1 2
2 3
2 4
4 5
1 3
3 5
1 5
[download]

Updates: Fix the /$Q/ test per Loops's suggestion. Add \b-s to s///.