We are asked to construct a graph with ~N~ nodes and ~M~ edges such that ~tns(1, N) = K~, where ~tns(x, y) = \sum_{C \in S_{x,y}} sgn(C)~. Let ~[a, b)~ be a set of nodes ~x~ such that there is a path from ~a~ to ~x~, there is a path from ~x~ to ~b~ and ~x~ is different from ~b~. We can remove the last element of each ordered array ~C \in S_{x,y}~ and obtain another ordered array ~C'~ that begins with ~x~, ends in some node from ~[x, y)~ and whose length is smaller by one than the length of ~C~, so ~sgn(C) = -sgn(C')~. Therefore ~tns(x, y) = -\sum_{z \in [x, y)} tns(x, z)~.

We will build our graph level-by-level. The first level will always contain a single node ~1~ and the last level will contain a single node ~N~. In the first two subtasks, all nodes (except ~N~) in a certain level will have directed edges towards all nodes in the next level. The general solution will be slightly modified.

The graph which solves the first subtask ~1 \le K < 500~ has three levels. The first level contains node ~1~, the second level contains ~K+1~ nodes, and the last level contains node ~K+3~. For example, for ~K = 4~ the graph looks like the one depicted below.

In this example, using the recurrence relation for ~tns(1, x)~, we can see that ~tns(1, 1) = 1~, ~tns(1, 2) = \dots = tns(1, 6) = (-1) \cdot 1~, ~tns(1, 7) = (-1) \cdot (1 + 5 \cdot (-1)) = 4~.

We will solve the second subtask with ~-300 < K \le -1~ in a similar manner. For example, for ~K = -4~ the graph looks like the one depicted below.

By inspecting the solutions for the first two subtasks we can observe that, by adding ~M~ nodes in a new level, we are multiplying the sum of all ~tns(1, x)~ values by ~-(M-1)~. It is also clear from the recurrence relation that ~tns(1, N)~ is equal to the sum of all ~tns(1, x)~ values, where ~1 \le x < N~, multiplied by ~-1~. If ~K~ has the form ~\pm 2^i~, by adding three nodes in a new level, the sum of ~tns(1, x)~ is multiplied by ~-2~ so we can obtain the value ~K~ up to its sign using ~3 + (i-1) \cdot 9~ nodes. If we get the wrong sign, we can simply add ~2~ nodes in the next level to multiply the solution by ~-1~.

All that is now left to determine is how to increase the absolute value of the current value by ~1~. Then we can use multiplications by ~2~ and additions by ~1~ to perform a popular algorithm for transposing the number from binary to its decimal notation. If the current sum is negative, we can simply subtract ~1~ by adding a new node to the current level that is connected with node ~1~. Similarly, if the sum is positive, we can add two nodes to a new level that are connected to all from the previous level, thereby negating the sum and subtracting ~1~ as described.

This algorithm constructs a graph for given ~K~ in less than ~16 \log_2(K)~ edges.