A. Aziz and Sardor's Game

Xotira: 32 MB, Vaqt: 1000 ms

Aziz and Sardor are playing a simple game. Aziz thought of number $x$ between $1$ and $n$, and Sardor tries to guess the number.

Sardor can ask questions like: "Is the unknown number divisible by number $y$?".

The game is played by the following rules: first Sardor asks all the questions that interest him (also, he can ask no questions), and then Aziz responds to each question with $a$ 'yes' or $a$ 'no'. After receiving all the answers Sardor should determine the number that Aziz thought of.

Unfortunately, Sardor is not familiar with the number theory. Help him find the minimum number of questions he should ask to make a guaranteed guess of Aziz's number, and the numbers $y_i$, he should ask the questions about.

4

3
2 4 3

6

4
2 4 3 5

B. Tree Consistency

Xotira: 32 MB, Vaqt: 1000 ms

A tree of size $n$ is an undirected connected graph consisting of $n$ vertices without cycles.

Consider some tree with $n$ vertices. We call a tree invariant relative to permutation $p = p_1  p_2... p_n$, if for any two vertices of the tree u and v the condition holds: "vertices u and v are connected by an edge if and only if vertices $p_u$ and $p_v$ are connected by an edge".

You are given permutation p of size $n$. Find some tree size $n$, invariant relative to the given permutation.

4
4 3 2 1

YES
4 1
4 2
1 3

3
3 1 2

NO

C. Coordinates on a Plane

Xotira: 32 MB, Vaqt: 1000 ms

On a plane are n points $x_i,y_i$ with integer coordinates between 0 and $10^6$. The distance between the two points with numbers a and b is said to be the following value: 

$$dist(a,b) = |x_a - x_b| + |y_a - y_b|$$

 (the distance calculated by such formula is called Manhattan distance).

We call a hamiltonian path to be some permutation pi of numbers from 1 to n. We say that the length of this path is value .

$$∑ ^ {n-1} _ {i=1} dist(p_i, p_{i+1})$$

Find some hamiltonian path with a length of no more than $25 × 10^8$. Note that you do not have to minimize the path length.

5
0 7
8 10
3 4
5 0
9 12

4 3 1 2 5

D. Frequent Flyer Flights

Xotira: 32 MB, Vaqt: 1000 ms

In the country there are exactly n cities numbered with positive integers from 1 to n. In each city there is an airport is located.

Also, there is the only one airline, which makes $m$ flights. Unfortunately, to use them, you need to be a regular customer of this company, namely, you have the opportunity to enjoy flight $i$ from city $a_i$ to city $b_i$ only if you have already made at least $d_i$ flights before that.

Please note that flight $i$ flies exactly from city $a_i$ to city $b_i$. It can not be used to fly from city $b_i$ to city $a_i$. An interesting fact is that there may possibly be recreational flights with a beautiful view of the sky, which begin and end in the same city.

You need to get from city 1 to city n. Unfortunately, you've never traveled by plane before. What minimum number of flights you have to perform in order to get to city n?

Note that the same flight can be used multiple times.

3 2
1 2 0
2 3 1

2

2 1
1 2 100500

Impossible

3 3
2 1 0
2 3 6
1 2 0

8

E. Outlining Borders

Xotira: 60 MB, Vaqt: 6000 ms

You are given an undirected graph consisting of $n$ ertices and $m$ edges. The vertices are numbered with integers from 1 to $n$, the edges are numbered with integers from 1 to $m$. Each edge can be unpainted or be painted in one of the $k$ colors, which are numbered with integers from 1 to $k$. Initially, none of the edges is painted in any of the colors.

You get queries of the form "Repaint edge $e_i$ to color $c_i$". At any time the graph formed by the edges of the same color must be bipartite. If after the repaint this condition is violated, then the query is considered to be invalid and edge $e_i$ keeps its color. Otherwise, edge $e_i$ is repainted in color $c_i$, and the query is considered to valid.

Recall that the graph is called bipartite if the set of its vertices can be divided into two parts so that no edge connected vertices of the same parts.

For example, suppose you are given a triangle graph, that is a graph with three vertices and edges (1, 2), (2, 3) and (3, 1). Suppose that the first two edges are painted color 1, and the third one is painted color 2. Then the query of "repaint the third edge in color 1" will be incorrect because after its execution the graph formed by the edges of color 1 will not be bipartite. On the other hand, it is possible to repaint the second edge in color 2.

You receive $q$ queries. For each query, you should either apply it, and report that the query is valid, or report that the query is invalid.

3 3 2 5
1 2
2 3
1 3
1 1
2 1
3 2
3 1
2 2

YES
YES
YES
NO
YES

F. Kamron and Binary String (Easy Version)

Xotira: 256 MB, Vaqt: 2000 ms

This is the easy version of the problem. The difference between the versions is that in this version, string tt consists of only '0' and '1'. You can hack only if you solved all versions of this problem.

Kamron has a binary string $s$ of length $n$. Kamron can perform the following operation:

• Choose two adjacent blocks of $s$ and swap them.

A block is a maximal $substring∗$ of identical characters. Formally, denote $s[l,r]$ as the substring $s_ls_{l+1}…s_r.$ A block is $s[l,r]$ satisfying:

• $l=1 or s_l≠s_{l-1}.$
• $s_l=s_{l+1}=…=s_r.$
• $r=n or s_r≠s_{r+1}.$

Adjacent blocks are two blocks $s[l_1,r_1]$ and $s[l_2,r_2]$ satisfying $r_1+1=l_2$.

For example, if $s=0001100111$, Kamron can choose the two blocks $s[4,5]$ and $s[6,7]$ and swap them, transforming $s$ into $0000011111$.

Given a string t of length n consisting of '0', '1' and '?', Kamron wants to determine the minimum number of operations required to perform such that for any index $i (1≤i≤n)$, if $t_i≠ '?'$ then $s_i=t_i$. If it is impossible, output $−1$.

∗∗A string a is a substring of a string b if a can be obtained from b by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1

1
3
1
-1
-1
-1

G. Kamron and Binary String (Hard Version)

Xotira: 32 MB, Vaqt: 1000 ms

This is the hard version of the problem. The difference between the versions is that in this version, string tt consists of '0', '1' and '?'. You can hack only if you solved all versions of this problem.

Kamron has a binary string $s$ of length $n$. Kamron can perform the following operation:

• Choose two adjacent blocks of $s$ and swap them.

A block is a maximal $substring∗$ of identical characters. Formally, denote $s[l,r]$ as the substring $s_ls_{l+1}…s_r.$ A block is $s[l,r]$ satisfying:

• $l=1 or s_l≠s_{l-1}.$
• $s_l=s_{l+1}=…=s_r.$
• $r=n or s_r≠s_{r+1}.$

Adjacent blocks are two blocks $s[l_1,r_1]$ and $s[l_2,r_2]$ satisfying $r_1+1=l_2$.

For example, if $s=0001100111$, Kamron can choose the two blocks $s[4,5]$ and $s[6,7]$ and swap them, transforming $s$ into $0000011111$.

Given a string t of length n consisting of '0', '1' and '?', Kamron wants to determine the minimum number of operations required to perform such that for any index $i (1≤i≤n)$, if $t_i≠ '?'$ then $s_i=t_i$. If it is impossible, output $−1$.

∗∗A string a is a substring of a string b if a can be obtained from b by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1

1
3
1
-1
-1
-1

6
010101
?0?0??
0101
?0?0
11100101
????????
11100101
???11?1?
1000100011
?11?000?0?
10101
?1011

2
-1
0
2
2
-1