<p>A company is organizing a meeting and has a list of <code>n</code> employees, waiting to be invited. They have arranged for a large <strong>circular</strong> table, capable of seating <strong>any number</strong> of employees.</p>

<p>The employees are numbered from <code>0</code> to <code>n - 1</code>. Each employee has a <strong>favorite</strong> person and they will attend the meeting <strong>only if</strong> they can sit next to their favorite person at the table. The favorite person of an employee is <strong>not</strong> themself.</p>

<p>Given a <strong>0-indexed</strong> integer array <code>favorite</code>, where <code>favorite[i]</code> denotes the favorite person of the <code>i<sup>th</sup></code> employee, return <em>the <strong>maximum number of employees</strong> that can be invited to the meeting</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/14/ex1.png" style="width: 236px; height: 195px;" />
<pre>
<strong>Input:</strong> favorite = [2,2,1,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong>
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> favorite = [1,2,0]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/14/ex2.png" style="width: 219px; height: 220px;" />
<pre>
<strong>Input:</strong> favorite = [3,0,1,4,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong>
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == favorite.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= favorite[i] &lt;=&nbsp;n - 1</code></li>
	<li><code>favorite[i] != i</code></li>
</ul>

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        # https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/solutions/1661178/python-explanation-with-pictures/
        # 1) form a one-way connected circle => maximum circle
        # 2) two mutal-favorting people => the sum of all the longest chain containing all the pairs



        # First, we find the largest circle.
        n = len(favorite)
        max_circle = 0
        seen = set()
        for i in range(n):
			# If a people hasn't been visited:
            if i not in seen:
                start = i
                cur_person = i
                curset = set()
				
				# As long as we are visiting new people, we keep finding his/her favorite.
                while cur_person not in seen:
                    seen.add(cur_person) 
                    curset.add(cur_person)
                    cur_person = favorite[cur_person]
					
				# Until we find the first visited people. Depends on if this 
				# visited people has been visited in eariler iteration or just this iteration.
                if cur_person in curset: # if current people is in current set, meaning we have found a new circle
                    cursum = len(curset)
					
					# use 'start' to find the distance from the first visited people in this iteration 
					# to this current people.
                    while start != cur_person: # tail cutting
                        cursum -= 1
                        start = favorite[start]
                    max_circle = max(max_circle, cursum)
                                       
		# Then we try to find the sum of largest arms. Firstly, find all mutal-favorite peoples.
        pair = []
        seen = set()
        for i in range(n):
		
			# If a is b's favorite and vise versa, we put them in 'pair'.
            if favorite[favorite[i]] == i and i not in seen: # prevent duplicates
                pair.append([i, favorite[i]])
                seen.add(i)# used
                seen.add(favorite[i]) # used
		
		# for every people I, find out all the people whos favorite is I.
        graph = collections.defaultdict(list)
        for i in range(n):
            graph[favorite[i]].append(i)


        max_arm = 0
        for x, y in pair:
            # max arm length start from first people a
            max_x = 0
            q = collections.deque()
            q.append([x, 0])
            #for follower in graph[x]: 
            #    if follower != y: # due to this, we need this initialization
            #        q.append([follower, 1])
            while q:
                cur, n = q.popleft()
                max_x = max(max_x, n)
                for nxt in graph[cur]:
                    if nxt != y:
                        q.append([nxt, n + 1])
                    
            # max arm length start from first people b
            max_y = 0
            q = collections.deque()
            q.append([y, 0])
            #for follower in graph[y]:
            #    if follower != x:
            #        q.append([follower, 1])
            while q:
                cur, n = q.popleft()
                max_y = max(max_y, n)
                for nxt in graph[cur]:
                    if nxt != x:
                        q.append([nxt, n + 1])
            
			# Thus the total length is the two longest arm plus 2 (a and b themselves)
            max_arm += 2 + max_x + max_y # cumulative as we can host many arms
			
		# select the larger one as the answer.
        return max(max_circle, max_arm)  
49300