For the first subtask, it is enough to print C 1 2. Either these people know each other or they don't. In either case, the crew will work together flawlessly.

For the second subtask, it is enough to make the ~5~ queries A 1 A 2 A 3 A 4 A 5. Now, the first ~6~ people form a complete graph, and we can apply this theorem on Wikipedia. Therefore, it is always possible to select a crew from the first ~6~ people. We can use brute force to find a crew.

For the third subtask, make the queries A 1 … A 80, then use brute force to find a crew. It is always possible to find a crew.

The fourth subtask is troll.

For the fifth subtask, the intended solution is to solve a more general version of the problem. Create a function ~\text{Solve}(V, a, b)~ where ~V~ is a set of people, ~a~ is an integer, and ~b~ is another integer. This function returns a subset of ~V~ that satisfies one of the following conditions:

• ~\text{Solve}(V, a, b)~ is a subset of ~V~ containing ~a~ people, and everyone in this subset knows each other.
• ~\text{Solve}(V, a, b)~ is a subset of ~V~ containing ~b~ people, and everyone in this subset does not know each other.

The answer to the problem is ~\text{Solve}(\{1,2,\dots,N\}, P, P)~.

You may find it easier to make ~\text{Solve}~ a recursive function.

You may find this proof of Ramsey's Theorem to be helpful in coding ~\text{Solve}~.

Let ~F(1,b)=1~ and ~F(a,1)=1~. Also, for ~a>1~ and ~b>1~, let ~F(a,b) = F(a-1,b) + F(a,b-1)~.

We show that for all ~a \ge 1~ and ~b \ge 1~, any set of ~F(a,b)~ people would satisfy at least one of these conditions:

• There exists a crew of size ~a~ that know each other
• There exists a crew of size ~b~ that don't know each other

The case where ~a=1~ or ~b=1~ is easy. The set is size ~1~. Pick this person from the set, and make a crew.

Let's solve the case where ~a>1~ and ~b>1~. Assume that ~F(a-1,b)~ and ~F(a,b-1)~ are already proven.

Ask the first person. Put all of the known people into a set ~S~, and all of the unknown people into set ~T~. Note that ~F(a,b) = 1 + |S| + |T|~ and ~F(a,b) = F(a-1,b) + F(a,b-1)~. So we have ~|S| + |T| = F(a-1,b) + F(a,b-1) - 1~.

Since ~|S| + |T| = F(a-1,b) + F(a,b-1) - 1~, we must have ~|S| \ge F(a-1,b)~ or ~|T| \ge F(a,b-1)~. So we have two cases.

• Case 1: ~|S| \ge F(a-1,b)~. We can use ~F(a-1,b)~ to create two cases.
  • Case 1a: We can find ~b~ people in ~S~ that don't know each other. In this case, we are already done.
  • Case 1b: There are ~a-1~ people in ~S~ that know each other. The first person knows everyone in ~S~, so we can form a crew with the first person and the ~a-1~ people in ~S~. Then there is a crew of ~a~ people that know each other, and we are done.
• Case 2: ~|T| \ge F(a,b-1)~. We can use ~F(a,b-1)~ to create two cases.
  • Case 2a: We can find ~a~ people in ~T~ that know each other. In this case, we are already done.
  • Case 2b: There are ~b-1~ people in ~T~ that don't know each other. The first person doesn't know anyone in ~T~, so we can form a crew with the first person and the ~b-1~ people in ~T~. Then there is a crew of ~b~ people that don't know each other, and we are done.

The last step is to use induction to finish off the proof. This step is easy and is left to the reader as a short exercise.

Note 1: You may notice that ~F(a,b) = \dbinom{a+b-2}{a-1}~. So in the function ~\text{Solve}~, you should have ~|V| \ge \dbinom{a+b-2}{a-1}~.

Note 2: You may notice that ~F(P,P) < N~ in all subtasks (so a solution always exists).

Note 3: We need to ask at most ~2P-3~ times. This is okay because ~2P-3 \le Q~ in all subtasks.