Counting House Arrangements on the Island

A mouse named Chirpy discovered a peculiar island. On this island, the inhabitants live in houses located along the edge of the island, and they rely on fishing. There are n houses labeled from \(1\) to \(n\) arranged on the boundary, and to exchange fish, the island has m intersections (labeled from \(n+1\) to \(n+m\)) located in the interior. In order to connect the towns, a total of \(n+m-1\) roads (edges) were built so that there is exactly one path between any two houses; that is, the road network forms a tree.

Furthermore, every intersection has at least three roads connected to it. Note that aside from intersections the roads do not cross each other, and there are no bridges or tunnels.

Due to a mishap, the map of the island was blown away. Fortunately, Chirpy still has a record of the endpoints of every road. Using these records, your task is to determine the number of distinct arrangements for the positions of the houses along the island's border. Two arrangements are considered identical if one can be obtained from the other by a rotation.

Hint: It can be shown that the number of possible circular orders is equal to \(\prod_{v \in I} (\deg(v)-1)!\), where \(I\) denotes the set of intersections (internal nodes) and \(\deg(v)\) is the degree of intersection \(v\).

inputFormat

The first line contains two integers n and m \( (1 \leq n, m \leq \text{small constraints})\), representing the number of houses and intersections respectively.

Each of the following \(n+m-1\) lines contains two integers \(u\) and \(v\) representing a road connecting nodes \(u\) and \(v\). The houses are numbered from \(1\) to \(n\), and the intersections are numbered from \(n+1\) to \(n+m\). It is guaranteed that the provided graph is a tree and that every intersection (node numbered \(n+1\) to \(n+m\)) has degree at least 3.

outputFormat

Output a single integer – the number of distinct arrangements of house positions (i.e. the circular order of the houses on the island's border), where two orders that can be obtained by rotation from one another are considered identical.

sample

3 1
1 4
2 4
3 4

2