The encyclopedia consists of N different web pages, numbered from 1 to N. There are M links present across the pages, the ith of which is present on page A[i] and links to a different page B[i].

A page may include multiple links, including multiple leading to the same other page.

A session spent on this website involves beginning on one of the N pages, and then navigating around using the links until you decide to stop. That is, while on page i, you may either move to any of the pages linked to from it, or stop your browsing session.

Assuming you can choose which page you begin the session on, what's the maximum number of different pages you can visit in a single session? Note that a page only counts once even if visited multiple times during the session.

Constraints:
2 <= N <= 500000
1 <= M <= 500000
1 <= A[i], B[i] <= N
A[i] != B[i]

Sample Test Case #1
N = 5
M = 6
A = [3, 5, 3, 1, 3, 2]
B = [2, 1, 2, 4, 5, 4]
Expected Return Value = 4

Sample Test Case #2
N = 10
M = 9
A = [3, 2, 5, 9, 10, 3, 3, 9, 4]
B = [9, 5, 7, 8, 6, 4, 5, 3, 9]
Expected Return Value = 5

Sample Explanation
In the first case, you can only visit at most 4 different page. For example, the sequence of pages 3 --> 5 --> 1 --> 4.
In the third case, you can only visit at most 5 different pages -− for example, the sequence of pages 3 --> 4 --> 9 --> 3 --> 5 --> 7 (note that page 3 only counts once).

The main difficulty in this problem is that the graph can be cyclic so I am not sure if DP can be applied.

I have the following recurrence:

Let's say that I have 1 array f and 1 function g. A function call to g takes O(1) time. Note that we do not want to edit the code of function g, its a scipy function. I just want to compute the values in the f array using the recurrence given below:

For simplicity, one can assume that the function g is similar to the binomial coefficient function. So, just for simplicity, assume that g(n, i) = number of ways of choosing i items from n items where n >= i. Is it possible to solve this assuming we can modify g and make some kind of recurrence?

f[n] = summation(f[n-i]*g(i, n)) for i in [1, 2, 3, 4, ..., n]

Base Case: f[0] = 1.

If we use the above recurrence, it will take O(n^2) time. Any way to reduce it to O(n*log(n)) ?

Thanks in advance.

This problem appeared in one of my university assignments, but I only know of one algorithm which is to find Shortest Distance from each node node to every other node using Dijkstra's Algorithm and take the maximum of all distances found in each iteration. This is going to take time = O(V(E+V)log(V)) which is too large for the given data set.

I don't understand what does the approach — "Instead, randomly select pairs of vertices and evaluate minimum weight path (also referred to as shortest path) between them", mentioned in the 4th question mean. Please help.!Here is the problem statement. I need help for the 4th problem.

Let's say we have 2 recurrence relations -
summation(a[i]*f[i] for i=1 to n1)+summation(b[i]*g[i] for i =1 to n2) = 0 --------> Equation 1
summation(c[i]*f[i] for i=1 to n3)+summation(d[i]*g[i] for i =1 to n4) = 0 --------> Equation 2
.
.
.
.
.
`-----------------------------------------------------------------------------------> Equation m
WHERE a[i], b[i], c[i] AND d[i] are constants.

##################################################################################################
In what cases is this above system of recurrence relations separable?
I want to express: f[i] in terms of only f terms and g[i] in terms of only g terms.
Is there a method to do it? If not, what are some of the specific cases under which this is doable?

I know of 1 such method when:
f[i]=a*f[i-1]+b*g[i-2] --------------------------------------------------Equation A
g[i]=c*f[i-5]+d*g[i-4] --------------------------------------------------Equation B
-> g[i-2]=(f[i]-a*f[i-1])/b -------------------------------------------- by rearranging A
-> f[i-5]=(g[i]-d*g[i-4])/c -------------------------------------------- by rearranging B
But now once you have say g[i-2]=(f[i]-a*f[i-1])/b, then by replacing i with i+2, we get,
-> g[i+2-2]=(f[i+2]-a*f[i+2-1])/b
-> g[i]=(f[i+2]-a*f[i+1])/b
Similarly g[i-4]=(f[i-2]-a*f[i-3])/b (from previous result)
now substitute these in Equation B.
Solve similarly for f.
Thus, separated.
##################################################################################################
Any general method?
Thanks in advance.

I have written the code to solve this problem, but it gives TLE. I think the complexity of my soln. is O(n). My approach is as follows:

Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from". dp[from][to] = 0, otherwise.

To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to". Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to". Otherwise, dp[from][to]=0;

Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from".

If no such "from" is found then answer="NO";

But this looks like O(n^2) solution. But, if we observe carefully, we see that each "from","to" pair of nodes corresponds to a directed edge going from node "from" to node "to". Since there are exactly n-1 edges, the no. of "from","to" pairs = 2*(n-1).

Here is my submission ----> http://mirror.codeforces.com/contest/764/submission/24382711.

NOTE: In this solution instead of passing -> "from","to" to dfs function, I have passed "from","index of 'to' in adj[from]". I have made multiple dfs calls but each call is computed exactly once, since I have made a vis[] array which keeps track of it.

NOTE: If we put a break statement in dfs for loop, we get AC. Lol :P Here is the AC submission. I don't know why it does not get TLE, as the time complexity remains the same, but it is slightly optimized.

Please tell where I am wrong in calculating the time complexity? Thanks in advance.

Here is my code for this problem — http://mirror.codeforces.com/contest/749/problem/D from Div-2 D round #388 Here is my submission --> http://mirror.codeforces.com/contest/749/submission/23178341 My code is well commented and as per the editorial given. It is taking too much time. The complexity is O(nlog(n)). How do I optimize my code? What operation/operations are taking too long ? Please Help! Thanks in advance.

I am trying to solve — http://mirror.codeforces.com/problemset/problem/721/C. Here is my submission — http://mirror.codeforces.com/contest/721/submission/22405854

I can't find what is wrong. I tried all small test cases (from codeforces) and it produced the right answer. Please Help!!

You have been given a n*n matrix consisting of 0's and 1's.You need to find the number of squares in the matrix such that it contains no 1's (All entries should be 0).

Constraints:
1=<n<=5000

Input:
First line consists of a single integer n.
Each of the next n lines consist of a binary string of length n.
Output:
Output just one integer, the answer as described above.

Sample:

Input:
3
000
000
000
Output:
14

Explanation: There are 9=> 1 * 1 squares, 4=> 2 * 2 squares and 1=> 3 * 3 square.

Input:
2
10
10
Output:
2

Explanation: There are 2=> 1 * 1 squares. All other squares contain a 1.

Input:
2
11
11
Output:
0

Input:
1
0
Output:
1