Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Divine Tree

By Nobel_ruettt · Limits 3s, 512 MB

One day Thor gave Nabil Bin Masterchief a rooted tree consisting of n vertices. Unfortunately, During the fight with Hela, his tree was shattered and he doesn't remember all it's edges. He only managed to restore m edges of the initial tree.

Now as a good friend of Nabil, you have to count the number of distinct trees of size n with vertex 1 as root which contain all of the m edges.


The first line of the input contains two integers n and m (1 ≤ n ≤ 13,** 0 ≤ m < n**) — the number of vertices and the number of edges remembered by Nabil respectively.

Each of the next m lines contains two integers Ui and Vi (1 ≤Ui,Vi n, Ui Vi) — the numbers of vertices connected by the i-th edge. It's guaranteed that this set of edges is a subset of edges of some tree. Same edge will not be given more than once in input.


Print a single integer — the number of trees of size n that contain all of the m edges.


5 2
4 1
4 2

3 1
2 1

Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn't occur in the other one.



    63% Solution Ratio

    YouKnowWhoEarliest, Aug '19

    YouKnowWhoFastest, 0.0s

    YouKnowWhoLightest, 131 kB

    ovis96Shortest, 545B


    Login to submit


    Approach 1: Counting, Prufer Code Theorem to find number of trees possible with n nodes Approach 2: ...

    Toph uses cookies. By continuing you agree to our Cookie Policy.