## CBOJ Exec Selection Contest 2 Problem 4 - George's Graph

Points: 10
Time limit: 0.5s
Memory limit: 256M

Author:
Problem type

For his CS homework, George was assigned the following problem:

You are given an intger $$N$$ and a directed graph consisting of $$N$$ vertices and $$\frac{N(N-1)}{2}$$ directed edges with no self-loops and the constraint that if the directed edge $$(u, v)$$ exists, then the directed edge $$(v, u)$$ does not exist, with $$u\ne v$$. Note that the directed edge $$(u, v)$$ indicates that there is a one-way edge from vertex $$u$$ to vertex $$v$$, however not the other way around. Additionally, you are given an integer $$Q$$, denoting the number of changes to the graph. In each of the $$Q$$ changes, a single integer $$x$$ is given, denoting that the $$x$$-th (one indexed) directed edge given in the input flipped (the edge is changed from $$(u, v)$$ to $$(v, u)$$). After each query, output the length of the longest path in the graph such that no vertices are visited more than once.

However, George has never listened to a CS lecture, so he has no clue how to solve it! Desperately, he comes to you asking for help. Can you help him?

Note: The changes to the graph are persistent. This means that the graph physically changes after each query and previous queries affect later queries.

#### Input

The first line consists of two space separated integers $$N$$ and $$Q$$, indicating the number of vertices in the graph and the number of queries, respectively.

The next $$\frac{N(N-1)}{2}$$ lines each consist of two space separated integers, $$u$$ and $$v$$, denoting that there exists a directed edge from $$u$$ to $$v$$.

The following $$Q$$ lines each contain a single integer $$x$$, indicating that the $$x$$-th (one indexed) edge given in the input is to be flipped.

#### Output

Output $$Q$$ lines, with the $$i$$-th line containing the length of the longest path in the graph such that no vertices are visited more than once after the change in the $$i$$-th query has been applied.

$$2 \le N \le 10^{2}$$

$$1\le Q \le 10^{2}$$

$$2 \le N \le 10^{3}$$

$$1 \le Q \le 10^{5}$$

3 1
1 2
2 3
1 3
3

3

#### Explanation for Sample Output 1

Although the graph forms a cycle of length $$3$$ after the change, the length of the longest in the case of this problem is $$3$$, since no vertices are to be visited more than once in the longest path.