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

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

Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.

&nbsp;
Example 1:

Input: favorite = [2,2,1,2]
Output: 3
Explanation:
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. 


Example 2:

Input: favorite = [1,2,0]
Output: 3
Explanation: 
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.


Example 3:

Input: favorite = [3,0,1,4,1]
Output: 4
Explanation:
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.


&nbsp;
Constraints:


	n == favorite.length
	2 &lt;= n &lt;= 105
	0 &lt;= favorite[i] &lt;=&nbsp;n - 1
	favorite[i] != i


class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        visited_time = [0] * n
        inpath = [False] * n
        cur_time = 1
        def get_max_len_cycle(cur) :
            nonlocal cur_time
            inpath[cur], visited_time[cur], nxt = True, cur_time, favorite[cur]
            cur_time += 1
            ret = 0 if not inpath[nxt] else visited_time[cur] - visited_time[nxt] + 1
            if visited_time[nxt] == 0 : ret = max(ret, get_max_len_cycle(nxt))
            inpath[cur] = False
            return ret
        
        ret_cycle = 0
        for i in range(n) :
            if visited_time[i] == 0 :
                ret_cycle = max(ret_cycle, get_max_len_cycle(i))
        
        ret_not_cycle = 0
        back_edge_graph = [[] for _ in range(n)]
        for i in range(n) : back_edge_graph[favorite[i]].append(i)
        def get_max_depth(cur) :
            ret = 0
            for nxt in back_edge_graph[cur] :
                if favorite[cur] != nxt :
                    ret = max(ret, get_max_depth(nxt) + 1)
            return ret
        
        for i in range(n) :
            if favorite[favorite[i]] == i : ret_not_cycle += get_max_depth(i) + 1
        
        ret = max(ret_cycle, ret_not_cycle)
        return ret
class Solution {
    public int maximumInvitations(int[] favorite) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < favorite.length; i++) {
            graph.add(new ArrayList<>());
        }

        int answer = 0;

        List<List<Integer>> pairs = new ArrayList<>();
        for (int i = 0; i < favorite.length; i++) {
            if (i == favorite[favorite[i]]) {
                if (i < favorite[i]) {
                    List<Integer> pair = new ArrayList<>();
                    pair.add(i);
                    pair.add(favorite[i]);
                    pairs.add(pair);
                }
            } else {
                graph.get(favorite[i]).add(i);
            }
        }

        boolean[] visited = new boolean[favorite.length];
        for (List<Integer> pair: pairs) {
            answer += dfs(graph, pair.get(0), visited) + dfs(graph, pair.get(1), visited);
        }

        int[] counter = new int[favorite.length];
        int[] round = new int[favorite.length];

        int rnd = 1;

        int circleMax = 0;

        for (int i = 0; i < favorite.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (round[i] != 0) {
                continue;
            }

            int cnt = 1;
            int j = i;
            while (counter[j] == 0) {
                counter[j] = cnt;
                round[j] = rnd;
                j = favorite[j];
                cnt++;
            }
            if (round[j] == rnd) {
                circleMax = Math.max(circleMax, cnt - counter[j]);
            }
            rnd++;
        }
        return Math.max(circleMax, answer);
    }

    private int dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        visited[node] = true;
        int max = 0;
        for (int neighbor: graph.get(node)) {
            max = Math.max(max, dfs(graph, neighbor, visited));
        }
        return max + 1;
    }
}
class Solution {
public:
    vector<vector<int>> rev;
    vector<int> es, sizeOfTwo;
    int N, ans1, ans2;
    void dfs(vector<int>& depth, int cur, int d) {
        if (depth[cur] > 0) {
            if (d - depth[cur] == 2) sizeOfTwo.push_back(cur);
            ans1 = max(ans1, d - depth[cur]);
            return;
        }
        if (depth[cur] != -1) return;
        depth[cur] = d;
        dfs(depth, es[cur], d+1);
        depth[cur] = 0; // 0 means visited
    }
    void findAllCircules() {
        vector<int> depth(N, -1);
        for (int i=0; i<N; i++) {
            if (depth[i] == -1) {
                dfs(depth, i, 1);
            }
        }
    }
    int dfs2(int cur, int except) {
        int ret = 1;
        int d = 0;
        for (auto nxt : rev[cur]) {
            if (nxt != except) {
                d = max(d, dfs2(nxt, except));
            }
        }
        return ret + d;
    }
    void expandSizeOfTwo() {
        for (auto i : sizeOfTwo) {
            int j = es[i];
            ans2 += dfs2(i, j);
            ans2 += dfs2(j, i);
        }
    }
    int maximumInvitations(vector<int>& favorite) {
        es = favorite;
        N = es.size(), ans1 = 0, ans2 = 0;
        rev.resize(N);
        for (int i=0; i<N; i++) {
            rev[es[i]].push_back(i);
        }
        findAllCircules();
        expandSizeOfTwo();
        return max(ans1, ans2);
    }
};
/**
 * @param {number[]} favorite
 * @return {number}
 */
var maximumInvitations = function(favorite) {
    let res = 0;
    let len = favorite.length;
    // count the number indegree
    let indegree = new Array(len).fill(0);
    // save the number relation
    let rMap = new Map();
    for(let i=0; i<favorite.length; i++){
        indegree[favorite[i]] ++;

        if(rMap.has(favorite[i])){
            let arr = rMap.get(favorite[i]);
            arr.push(i);
            rMap.set(favorite[i], arr);
        }else{
            rMap.set(favorite[i], [i]);
        }
    }
    // find the 0 indegree number
    let arr = [];
    for(let i=0; i<len; i++){
        if(indegree[i] === 0){
            arr.push(i);
        }
    }
    // check if the circle exist
    let search = 0;
    // the length of uncircle
    let l = 1;
    // save the number and the length of uncircle
    let lMap = new Map();
    while(arr.length > 0){
        let tmp = [];
        for(let i=0; i<arr.length; i++){
            lMap.set(arr[i], l);
            let next = favorite[arr[i]];
            indegree[next] --;
            search ++;
            if(indegree[next] === 0){
                tmp.push(next);
            }
        }
        // update the length of uncircle
        l ++;
        arr = [...tmp];
    }

    if(search === len){
        // circle not exist
    }else{
        // circle exist
        // find the not 0 indegree number
        let keys = find(indegree);
        // mark the search number in circle
        let circleMap = new Map();
        // the length of circle
        let circleLen = 1;
        // the max length of circle
        let maxCircleLen = 0;
        // sum the length of circle
        let sumCircleLen = 0;
        let cArr = [keys[0]];

        while(cArr.length > 0){
            let tmp = [];
            for(let i=0; i<cArr.length; i++){
                // not find the circle
                if(!circleMap.has(cArr[i])){
                    circleMap.set(cArr[i], circleLen);
                    tmp.push(favorite[cArr[i]]);
                // find the circle
                }else{
                    maxCircleLen = Math.max(maxCircleLen, circleLen-1);
                    // if the length equals 2 then sum the length
                    if(circleLen-1 === 2){
                        let m = calc(cArr[i], rMap, lMap) + calc(favorite[cArr[i]], rMap, lMap) + 2;
                        sumCircleLen += m;
                    }
                    // reset the length
                    circleLen = 0;
                    // find the next number not search
                    for(let i=0; i<keys.length; i++){
                        if(!circleMap.has(keys[i])){
                            tmp.push(keys[i]);
                            break;
                        }
                    }
                }
            }
            circleLen ++;
            cArr = [...tmp];
        }
        res = Math.max(res, maxCircleLen, sumCircleLen);
    }

    return res;
};

function calc(num, rMap, lMap){
    let res = 0;
    let arr = rMap.has(num) ? rMap.get(num) : [];
    if(arr.length > 0){
        for(let i=0; i<arr.length; i++){
            let l = lMap.has(arr[i]) ? lMap.get(arr[i]) : 0;
            res = Math.max(res, l);
        }
    }
    return res;
}

function find(arr){
    let res = [];
    for(let i=0; i<arr.length; i++){
        if(arr[i] > 0){
            res.push(i);
        }
    }
    return res;
}
Maximum Employees to Be Invited to a Meeting