Suppose you are at a party with N people and among them, there may exist one celebrity. The definition of a celebrity is that all the other N - 1 people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information about whether A knows B.

You need to find out the celebrity (or verify there is not one) by asking as few questions as possible. Assume that all of the guests at the party are polite (even the celebrity) and answer any question with the correct answer.

What is the maximum number of questions your algorithm needs to solve this problem?

Option 1 : N - 1
Option 2 : N log N
Option 3 : 3N - 3
Option 4 : 2N - 2

Whichever option is correct, just submit the integer value. For example:
if option 1 is correct then submit '1' 
if option 2 is correct then submit '2'