Who's Going? Can you help me? If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?

Challenge

Given a list of several pairings of people, such that in each pairing the second person goes if the first person goes, and a positive integer number of people who go, determine one or all possibilities of who goes. You may output either, as long as the output is consistent.

The example above may be represented in input by [(A,B),(A,D),(B,C),(C,D),(D,E)],3, which can be represented as a graph visually as:

A -&gt; B -&gt; C -&gt; D -&gt; E
⤷-------------⤴ 


If A goes, then everyone must go, so at least 5 people go, which cannot be 3 people.

If B goes, then C, D, and E must go, so at least 4 people go, which cannot be 3 people.

Thus we are left with C, D, and E going, yielding a final output of [C,D,E].

The input [(0,1),(0,3),(1,2),(2,3),(3,4)],3 represents the same situation and is the format given in the test cases (with output [2,3,4]).

We assume that no people other than the people in at least one pairing should be considered. For example, there is no person 5 or F in this example.

I/O

Your program/function must input g, the list of pairings which represents a directed graph, and n, the number of people who will go. Input g may be taken in any format (such as an adjacency matrix) which does not encode additional information and can encode at least 25 people to consider (the example considered 5 people). 

You may also (optionally) input p, the list of people, and/or c, the number of people to consider. List of people p given g (sorted). (append L to end to get number of people c).

Your program/function does not have to handle if:


the integer input is greater than the number of people considered.
the integer input is not positive
repeat pairings
reflexive pairings (e.g. (A,A) or (0,0))
impossible situations (e.g. [(A,B),(B,A)],1)


The output should be in any format which can represent a list from 1 to 24 people.

Test Cases

If the output of a test case has an OR in it, your program may return any one or all of the choices.


[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 1 => [3] OR [4]
[(0,1),(1,2)], 1 => [2]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 1 => [7]
[(1,2),(2,3)], 2 => [2,3]
[(1,2),(3,4)], 2 => [1,2] OR [3,4] OR [2,4]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 1 => [7] OR [15]
[(0,1),(1,0),(0,2),(1,3)], 1 => [2] OR [3]
[(0,1),(1,0),(0,2),(1,3)], 2 => [2,3]
[(0,1),(1,2)], 3 => [0,1,2]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 4 => [8,9,4,7]
[(0,1),(1,0),(0,2),(1,3)], 4 => [0,1,2,3]
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 5 => [3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 5 => [4,5,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 6 => [2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 7 => [1,2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 7 => [3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 8 => [2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 9 => [1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 9 => [14,15,16,17,18,21,22,23,24]
Husk, 14 10 bytes

~f`öΠFf†€Ṗ


Takes three inputs: number of people to go, 2-row matrix of the constraints, and list of all people involved, in this order.
Returns all possible lists of people who go.
If you want to output only one list, replace the leftmost f by ḟ.
Try it online!

Explanation

The idea is to loop over the size-n subsets of p and keep those that satisfy the condition imposed by g: if the first person in a pair goes, then the second person must go too.

~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3


This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try.
First, n is the first argument, so it can be given to Ṗ directly, making it a function that takes a list and returns its n-subsets.
The next two inputs are g and p, and the program's shape at this point is ~(f)(`öΠFf†€)(Ṗn) with parentheses added for clarity.
The operator ~ gives g to `öΠFf†€ and p to Ṗn, and combines the results with f.
Ṗnp is just the n-subsets of p, so that's simple.
The operator ` causes öΠFf†€ to take its arguments in the reverse order, so g is actually the second argument of this function.
The first argument is an element q of Ṗnp, which is extracted by f (filter).
We give q as an argument to €, which becomes a function for testing membership in q, and deep map that over the second argument, which is g.
Then ΠFf are applied to the result.
The role of ö is just to compose ΠFf†€ into one function, which we can then pass on to ` and ~f.