Treasure

Canmuu and his friends have gathered a large cache of plutonium and plan to bury their treasure at some road intersection deep in the Canadian wilderness. Every buried treasure needs a treasure map, so they decide to draw one of their own.

The road network has $N$ intersections (numbered $1$ through $N$) joined by exactly $N$ roads. Every intersection has at least one road and at most four roads, and the network is connected: a moose can travel between any pair of intersections. Because heavy traffic would compromise secrecy, the treasure is never buried at a 4-way intersection (an intersection with exactly four roads).

The map shows all of the roads and all of the intersections, but to hide the treasure only a single intersection is labeled with a big red "X": the one where the treasure is buried.

Canmuu draws a trial map for each possible burial spot and notices that two different burial spots can produce maps that look the same. The herd wonders how many genuinely different maps they could end up with.

Two maps are considered the same when the intersections of one map can be matched one-to-one with the intersections of the other so that:

• the two X-labeled intersections are matched with each other, and
• under this matching, every road of one map corresponds to a road of the other.

For example, when $N = 4$ the treasure could be buried at any of the four intersections:

        +             +             X           +
       /|            /|            /|          /|
  X---+ |       +---X |       +---+ |     +---+ |
       \|            \|            \|          \|
        +             +             +           X

The last two maps are not different: flipping one of them upside down matches every intersection and every road. So only three of the four maps are distinct.

Given the road network, determine how many distinct treasure maps are possible.

Constraints: $4 \le N \le 100{,}000$; each intersection has between $1$ and $4$ roads; the network is connected and has exactly $N$ roads.

• Line 1: a single integer $N$.
• Lines 2 to $N+1$: two space-separated integers $A$ and $B$ ($1 \le A \le N$, $1 \le B \le N$), meaning that a road connects intersections $A$ and $B$.

• A single integer: the number of distinct treasure maps.