Gerrymandering with Logic Gates The majority function is a boolean function which takes three boolean inputs and returns the most common. For instance if maj(x,y,z) is the majority function and T denotes true and F denotes false then:

maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F


This question concerns writing boolean functions as compositions of majority functions. An example of a 5-ary composition of majority functions is (x1,x2,x3,x4,x5) =&gt; maj(x1,x2,maj(x3,x4,x5)). This function returns the following output on these sample input vectors:

(T,T,F,F,F) =&gt; maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) =&gt; maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) =&gt; maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) =&gt; maj(F,F,maj(F,T,T)) = maj(F,F,T) = F


Task

Write a program which inputs a positive integer n and a list of length n vectors of booleans and outputs a tree of majority gates that returns true on all of the given vectors if possible.  The function may return either true or false on vectors not in the list of constraints.


The list of vectors may be input in any format you like. If you prefer, instead of inputting the vector, you may input the list of true positions in the vector. So for instance, [TTF,TFT,FTT] or [[T,T,F],[T,F,T],[F,T,T]] or [[1,2],[1,3],[2,3]] (list of true positions) are all fine.
Output can be any valid tree format. For instance, maj(maj(x1,x2,x3),x4,x5) works. You will probably want to use single numbers as stand-ins for variables, as in [[1,2,3],4,5]. Reverse polish 123m45m is also okay, for instance.
If there is no function that works, your program should generate an error or output a falsey value.
If there are multiple functions that work, your program can return any of them. The function does not need to be simplified. For instance, maj(x1,x1,x2) or x1 are equivalent.


Scoring

This is code golf: Shortest solution in bytes wins.

Test cases:

Note that there are many possible outputs for each of these cases, so you should write a checker script that converts your output to a function and check that your function returns true on each of the specified input vectors.

Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent

Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)

Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent

Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent

Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error

Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options

Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options 

Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others

Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others

Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
JavaScript (ES6), 260 bytes

Takes input as an array of arrays of booleans. Returns a tree of 1-indexed majority gates or throws a recursion error (1) if no solution exists.

The main function f() recursively attempts to find a solution by calling the solver F() and incrementing the maximum nesting level m at each iteration.

(1) after a long time, and assuming infinite memory

f=(a,m)=&gt;(F=(a,d,I=a[i=0].map(_=&gt;++i),g=(a,b)=&gt;b[1]?b.reduce((s,i)=&gt;s+g(a,i),0)&gt;1:a[b-1])=&gt;I.find(i=&gt;a.every(a=&gt;g(a,i)))||d&amp;&amp;(I.reduce((a,x)=&gt;[...a,...a.map(y=&gt;[...y,x])],[[]]).some(b=&gt;r=b.length==3&amp;&amp;F(a.map(a=&gt;[...a,g(a,b)]),d-1,[...I,b]))&amp;&amp;r))(a,m)||f(a,-~m)


Demo



f=(a,m)=&gt;(F=(a,d,I=a[i=0].map(_=&gt;++i),g=(a,b)=&gt;b[1]?b.reduce((s,i)=&gt;s+g(a,i),0)&gt;1:a[b-1])=&gt;I.find(i=&gt;a.every(a=&gt;g(a,i)))||d&amp;&amp;(I.reduce((a,x)=&gt;[...a,...a.map(y=&gt;[...y,x])],[[]]).some(b=&gt;r=b.length==3&amp;&amp;F(a.map(a=&gt;[...a,g(a,b)]),d-1,[...I,b]))&amp;&amp;r))(a,m)||f(a,-~m)

test = a =&gt; console.log(JSON.stringify(f(a.split(',').map(s =&gt; [...s].map(c =&gt; c == 'T')))))

test('TFF')
test('TTF,TFT')
test('TTF,TFT,FTT')
test('TTTF,TTFT,TFTT,FTTT')
test('TTTFF,FTTFT,TFFFT')
test('TTTFFF,FTFTTF,TFFTFT')
test('TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT')




Example

Below is a validation table of the solution found for the last test case of the demo.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --&gt; [F,T,[T,F,T]] -&gt; [F,T,T] --&gt; T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --&gt; [F,T,[F,T,T]] -&gt; [F,T,T] --&gt; T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --&gt; [T,T,[F,F,T]] -&gt; [T,T,F] --&gt; T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --&gt; [F,T,[T,T,T]] -&gt; [F,T,T] --&gt; T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --&gt; [T,F,[T,F,T]] -&gt; [T,F,T] --&gt; T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --&gt; [T,T,[F,T,F]] -&gt; [T,T,F] --&gt; T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --&gt; [F,T,[T,T,T]] -&gt; [F,T,T] --&gt; T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --&gt; [T,F,[T,F,T]] -&gt; [T,F,T] --&gt; T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --&gt; [T,T,[F,T,F]] -&gt; [T,T,F] --&gt; T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --&gt; [T,F,[T,T,F]] -&gt; [T,F,T] --&gt; T