Problem H
Organising the Organisation
Input: Standard Input
Output: Standard Output
Time Limit: 2 Second
I am the chief of the Personnel
Division of a moderate-sized company that wishes to remain anonymous, and I am
currently facing a small problem for which I need a skilled programmer's help.
One of the divisions is Central Management
(division A in the figure above), and should of course be at the top of the
hierarchy, but the relative importance of the remaining divisions is not
determined, so in Figure 1 above, division C and D could equally well have
switched places so that C was in charge over division D. One complication,
however, is that it may be impossible to get some divisions to cooperate with
each other, and in such a case, neither of these divisions can be directly in
charge of the other. For instance, if in the example above A and D are unable
to cooperate, Figure 1 is not a valid way to organise the company.
In general, there can of course be many different
ways to organise the organisation, and thus it is desirable to find the best
one (for instance, it is not a good idea to let the programming people be in
charge of the marketing people). This job, however, is way too complicated for
you, and your job is simply to help us find out how much to pay the consultant
that we hire to find the best organisation for us. In order to determine the
consultant's pay, we need to find out exactly how difficult the task is, which
is why you have to count exactly how many different ways there are to
organise the organisation.
Oh, and I need the answer in five hours.
The input consists of a series of test cases, at
most 50, terminated by end-of-file. Each test cases begins with three
integers n, m, k (1 ≤ n ≤ 50, 0 ≤ m ≤ 1500, 1 ≤ k ≤ n). n denotes the number of divisions in the company (for
convenience, the divisions are numbered from 1 to n), and k
indicates which division is the Central Management division. This is followed
by m lines, each containing two integers 1 ≤ i, j ≤ n,
indicating that division i and division j cannot cooperate (thus,
i cannot be directly in charge of j and j cannot be
directly in charge of i). You may assume that i and j are
always different.
For each test case, print the number of possible ways to organise the company on a line by itself. This number will be at least 1 and at most 1015.
5 5 2 3 1 3 4 4 5 1 4 5 3 4 1 1 1 4 3 0 2 |
3 8
3 |
Problem setter: Per Austrin