407941: GYM102946 H Halting Problem

Hans the shark lives in an underwater country that is divided into $$$n$$$ states, numbered from 1 to $$$n$$$. There are $$$m$$$ bidirectional roads in this country, each of which connects two different states. It is possible to travel from any state to any other state by swimming along the roads.

Hans is planning some journeys around the country. He first chooses a set of states in the country, and calls them the "halting states". Then he defines a "journey" as follows:

1. He chooses any halting state as the start state. It is his initial current state.
2. For each day, he chooses some state such that it is connected with his current state by a road. He then swims along that road, so the chosen state becomes the new current state.
3. After swimming along a road, if the current state is a halting state and is not the start state, then he may choose to end the journey immediately (he may also choose to not end).

In other words, a journey is a walk that starts from a halting state and ends in a different halting state. A walk consists of a sequence of states in which every two adjacent states are connected by a road.

The length of a journey is defined as the number of days spent before it ends, which is also the total number of roads he has traveled. A journey is called "happy" if its length is a multiple of $$$k$$$, where $$$k$$$ is Hans' lucky number. Hans wants to choose the maximum number of halting states, such that every possible journey that ends is happy. Can you help him do it?

The first line contains three integers $$$n, m, k$$$. Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ describing a road between the states numbered $$$u_i$$$ and $$$v_i$$$.

Technical specifications:

• $$$2 \le n \le 2 \times 10^5$$$
• $$$n - 1 \le m \le \min(2 \times 10^5, \frac{n(n-1)}{2})$$$
• $$$1 \le k \le 2 \times 10^5$$$
• $$$1 \le u_i < v_i \le n$$$ for $$$i=1,2,\dots,m$$$
• $$$(u_i, v_i) \ne (u_j, v_j)$$$ when $$$i \ne j$$$

Output one integer, the maximum number of halting states that Hans can choose such that every possible journey that ends is happy.

5 6 2
1 3
1 5
2 5
2 3
2 4
1 4

3

4 3 3
1 2
2 3
3 4

1

Remember that if no journey can possibly end, then the constraint is satisfied.

In the first example, Hans can choose the states 3, 4, and 5. He can also choose the states 1 and 2, but the number of halting states is not maximized.

In the second example, the maximum number of halting states is 1, as Hans cannot choose more than 1 halting states. For example, if the states 1 and 4 are chosen, then there exists a journey $$$1\rightarrow2\rightarrow3\rightarrow2\rightarrow3\rightarrow4$$$ which has length 5 so is not happy. On the other hand, if state 1 is the only halting state, then no journey can possibly end, so every journey that ends is happy.