Ok so if we try to make a graph following these constraints we can only do a linked list (where every node is sequentially linked to each other like 1-2-3-6-4-5) or a linked list where the to nodes in the sides are connected (im going to call that a cycle and write it as -1-2-3-6-4-5- [imagine that the '-' in the side are connected]). Let's tackle each type seperately:

• Notice that every single possible normal linked list is a permutation in the order that the nodes are connected to each other. For example if we don't count the loops and n = 3, then the possibilities are 1-2-3, 1-3-2, 2-1-3, or n!/2. The possibilities 3-2-1, 2-3-1 and 3-1-2 are just the same possibilities we already counted reflected, so we actually need to divide by two to not count those

• A similar idea aplies to cycles, but we need to be careful with things like -1-2-3- and -3-1-2- being the same possibility because they just loop around. We can fix the first number in our cycle to be 1, as we can always turn it arround and make 1 be the first one, and then the number of cycles will be the number of ways to permute all the remaining n-1 nodes, or (n-1)!.

That way, the answer is n!/2 + (n-1)!. We can calculate that on linear time which makes me wonder why n is lower than 300, maybe i got it wrong :P (could you send a link to the problem so i can see it?)

Hope it helped!